Che materia stai cercando?

Appunti Architettura ed Elaboratori

Dispensa di Architettura ed Elaboratori con varo esercizi, alla fine del pdf sono presenti esercizi svolti per il primo e secondo compitino, dal 2008 al 2014 basati su appunti personali del publisher presi alle lezioni del prof. Silvestri dell’università degli Studi di Padova - Unipd. Scarica il file in formato PDF!

Esame di Architettura ed Elaboratori docente Prof. F. Silvestri

Anteprima

ESTRATTO DOCUMENTO

1

16

Introduzione al corso di Architettura

degli Elaboratori

A. Rodà

(adattamento da G. Chiola)

Architettura degli Elaboratori © 2013

Elaboratore elettronico 2

16

• Un elaboratore elettronico è una macchina

automatizzata per l’elaborazione di dati, numerici o

di altro tipo

• Macchina di tipo «universale», capace cioè di

eseguire diversi programmi per la risoluzione di

una grande varietà di problemi

Architettura degli Elaboratori © 2013

Un primo esempio di macchina... 3

• Si adatta a differenti tipi di 16

bucato.

programmata mediante un

• Viene

linguaggio fatto da singole parole

- "Cotone", "Colorati", "Sintetici", "Lana".

• Non esegue controlli

- è compito dell’utente impartire ordini

corretti leggendo prima il manuale d’uso.

• Anche impartendo ordini corretti

la macchina potrebbe non dare i

risultati aspettati -> guasto.

Architettura degli Elaboratori © 2013

Un primo esempio di macchina... 4

• Se la macchina si guasta, il tecnico della manutenzione userà

descrizioni dello stesso elettrodomestico diverse dal manuale 16

d'uso

- schemi elettrici, catalogo delle parti, ecc.

• Utilizzerà quindi un modo diverso di osservare e manipolare la

stessa macchina -> un diverso livello di astrazione.

Architettura degli Elaboratori © 2013

Preparare una pizza... 5

• Per cucinare una pizza occorre procurarsi gli 16

ingredienti, la ricetta, ed una serie di

attrezzi.

• La ricetta farà uso di un linguaggio che

dobbiamo essere in grado di comprendere e

dovrà descrivere il procedimento in termini di

passi elementari che dobbiamo essere in grado

di realizzare.

• In termini informatici, la realizzazione di una

pizza seguendo passo passo le indicazioni di

una ricetta costituisce una attività detta

interpretazione da parte di una macchina

virtuale (noi stessi nella fattispecie).

Architettura degli Elaboratori © 2013

Preparare una pizza... 6

• Talvolta potremmo aver bisogno di istruzioni più dettagliate 16

per portare a termine un’operazione (ad es. “scaldare il

forno”).

• L'eventuale interruzione della interpretazione della ricetta

per leggere su un altro manuale le istruzioni dettagliate di

accensione e regolazione della temperatura, in termini

estensione procedurale, per

informatici costituisce una

sopperire ad una mancanza di corrispondenza tra le

istruzioni contenute nella ricetta (programma da eseguire)

e l'insieme delle istruzioni che la macchina virtuale (noi

stessi) conosce ed é in grado di eseguire direttamente.

• Al termine dell'interpretazione della procedura "scaldare il

forno" la macchina virtuale può tornare all'interpretazione

del programma principale, dal punto in cui l'aveva

interrotto.

Architettura degli Elaboratori © 2013

In pizzeria... 7

• In pizzeria l'interazione avviene con un 16

cameriere, il quale assume agli occhi del

macchina virtuale

cliente il ruolo di

• Il linguaggio usato per la comunicazione

cliente-cameriere sarà quello dei nomi delle

linguaggio ad alto

pizze scritte sul menù ->

livello

• Ordinando al cameriere una “quattro

stagioni" comandiamo alla macchina virtuale

pizzeria l'esecuzione di una attività

complessa, il cui risultato é quello di far

arrivare al tavolo la pizza desiderata,

disinteressandosi dei dettagli

Architettura degli Elaboratori © 2013

In pizzeria... 8

16

• Il cameriere scriverà l'ordine su un pezzo di carta

codificare in forma

usando delle convenzioni per

abbreviata l'ordine.

• Il cameriere, passato l’ordine, può dedicarsi a

servire un altro tavolo, demandando quindi il

completamento dell'esecuzione dell'istruzione ad

un'altra macchina virtuale (il pizzaiolo) -> catena di

pipeline.

montaggio, che gli informatici chiamano

Architettura degli Elaboratori © 2013

In pizzeria... 9

• La macchina virtuale pizzaiolo interpreta gli ordini ricevuti dal cameriere 16

applicando una serie di passi elementari che ha imparato ad eseguire una

volta per tutte e che ricorda in permanenza (stendere la pasta, aggiungere

la passata di pomodoro, aggiungere la mozzarella, ecc.).

• In termini informatici, il pizzaiolo esegue una istruzione della sua macchina

micro istruzioni presenti in una sua

virtuale interpretando una sequenza di

memoria permanente (firmware) ed univocamente associate a ciascun codice

che il cameriere scrive sull'ordine.

• L'esecuzione delle micro istruzioni può essere interrotta solo nel caso si

manifestino delle eccezioni (o trap), ad esempio per esaurimento degli

ingredienti o per mancato riconoscimento del codice di un comando.

• Il trattamento di una eccezione può comportare un ritardo nel

completamento dell'esecuzione del comando (per esempio chiedendo a voce

al cameriere di chiarire cosa c’era scritto nella comanda) o l'aborto (col

cameriere che torna dal cliente e si scusa di non poter soddisfare l'ordine a

causa dell'esaurimento dei carciofini).

Architettura degli Elaboratori © 2013

Stratificazione a livelli 10

• Storicamente si é venuta consolidando una 16

stratificazione dei livelli di astrazione utilizzati

per progettare e per descrivere un sistema di

calcolo

- L 5 Linguaggi di alto livello

- L 4 Assembler

- L 3 Nucleo del Sistema Operativo

- L 2 Macchina convenzionale

- L 1 Micro Architettura o Trasferimento tra Registri

- L 0 Logica Circuitale

- L-1 Elettronica Circuitale e/o Fotonica

- L-2 Fisica dello stato solido

Architettura degli Elaboratori © 2013

Stratificazione a livelli 11

• L 5 Linguaggi di alto livello 16

- Il livello di macchina virtuale normalmente usato dal programmatore di

applicazioni eseguite dal sistema di calcolo;

• L 4 Assembler

- Il livello di macchina virtuale più basso utilizzabile dal programmatore

di applicazioni eseguite dal sistema di calcolo;

• L 3 Nucleo del Sistema Operativo

- Il livello di macchina virtuale che permette l'attivazione di programmi

indipendenti (processi) e l'uso delle risorse fisiche del sistema da

parte di questi programmi, senza interazioni logiche tra loro;

• L 2 Macchina convenzionale

- Il livello di definizione delle istruzioni base del computer e degli altri

dispositivi fisici che compongono il sistema;

Architettura degli Elaboratori © 2013

Stratificazione a livelli 12

• L 1 Micro Architettura o Trasferimento tra Registri 16

- Il livello di definizione del funzionamento dei singoli componenti

fisici del sistema in termini di interconnessione e spostamento di

informazioni tra circuiti logici elementari;

• L 0 Logica Circuitale

- Il livello di realizzazione dei circuiti logici elementari basato sulla

logica Booleana;

• L-1 Elettronica Circuitale e/o Fotonica

- Il livello di progettazione dei circuiti logici elementari in termini di

transistor o dispositivi optoelettronici;

• L-2 Fisica dello stato solido

- Il livello di progettazione dei dispositivi elettronici integrati sulla

base delle caratteristiche fisiche dei semiconduttori.

Architettura degli Elaboratori © 2013

Stratificazione a livelli 13

Fondamenti di informatica

L 5 Linguaggi di alto livello 16

L 4 Assembler Sistemi operativi

L 3 Nucleo del Sistema Operativo

L 2 Macchina convenzionale

L 1 Micro Architettura o Trasferimento tra Registri

L 0 Logica Circuitale

L-1 Elettronica Circuitale e/o Fotonica

L-2 Fisica dello stato solido Corsi di elettronica

Architettura degli Elaboratori © 2013

Corso di Architettura degli elaboratori 14

L 5 Linguaggi di alto livello 16

L 4 Assembler

L 3 Nucleo del Sistema Operativo

L 2 Macchina convenzionale

L 1 Micro Architettura o Trasferimento tra Registri

L 0 Logica Circuitale

L-1 Elettronica Circuitale e/o Fotonica

L-2 Fisica dello stato solido

Architettura degli Elaboratori © 2013

Programma del corso 15

• Reti logiche (combinatorie e sequenziali) -> L0 16

• Architettura ed organizzazione degli elaboratori -> L1

• Istruzioni di macchina -> L2

- PD32

• Introduzione al linguaggio assembly -> L4

- Il processore ARM:

- Samsung S3C2440

- Attività di laboratorio: uso del linguaggio assembly

Architettura degli Elaboratori © 2013

16

16

Fine

Introduzione al corso di

Architettura degli Elaboratori

Architettura degli Elaboratori © 2013

Testo di rif.to:

[Congiu] - 1.1 (pg. 1–17)

Rappresentazione delle informazioni

-1.g Informazioni numeriche

Rappresentazione delle informazioni 1

Stringa di 32 bit nella memoria di un elaboratore:

11100000100000010010000000000000

Cosa rappresenta? Dipende ... 40

32

certamente una di 2 =4294967296 (4G) possibili cose diverse:

un’istruzione ARM:

• add r2, r1, r0

un numero naturale (in base 2):

• 4034994176

10

un numero intero (complemento a 2):

• -259973120

10

un numero razionale (floating point):

• 66

-74435494641179600000 (-1,0087890625 )

×2

10 10

una stringa di 4 caratteri (ASCII):

• ‘<SOH> <NUL>

una stringa di 4 caratteri (ASCII estesa):

• ü <NUL>

a

uno di 4G possibili colori diversi di un pixel

• . . .

• © 2017

Architettura degli Elaboratori

Cosa vedremo 2

1. I sistemi di numerazione

• Decimale, binario, esadecimale… 40

• Conversioni di base

2. Le informazioni numeriche

• Numeri naturali (senza segno o “unsigned”)

• Numeri interi (con segno o “signed”)

• Numeri non interi (Þ fixed-/floating-point)

3. Le informazioni non numeriche

• Testi, immagini, suoni, video… © 2017

Architettura degli Elaboratori

Il sistema posizionale 3

(… .a =

a a a a …) b

2 1 0 -1 -2 40

2 1 0 -1 -2

= + + + + +…

…+ a ·b a ·b a ·b a ·b a ·b

2 1 0 -1 -2

i

= a ·b

S i i

• è la base del sistema di numerazione

b

• Gli sono le cifre del numero

a i

• Il valore di una cifra dipende

dalla sua posizione © 2017

Architettura degli Elaboratori

Sistema decimale 4

• b=10 40

• Possibili cifre: {0;1;2;3;4;5;6;7;8;9}

3

2095.42 = 2 · 10 +

10 2 +

0 · 10

9 · 10 +

5 +

4 / 10 +

2

2 / 10 © 2017

Architettura degli Elaboratori

Sistema binario 5

• b=2 40

• Possibili cifre: {0;1} 4

= 1 · 2 +

11011.101

2 3

1 · 2 +

2

0 · 2 +

1 · 2 +

1 +

1 / 2 +

2 +

0 / 2 3 = 27.625

1 / 2 10 © 2017

Architettura degli Elaboratori

Sistema ottale 6

• b=8

• Possibili cifre: {0;1;2;3;4;5;6;7} 40

2

= · 8 +

3

375.1

8 · 8 +

7 +

5 / 8 =

1 253.125

10

Una cifra ottale può rappresentare 3 cifre binarie:

110 011 101 001 110011101001 = 6351

2 8

6 3 5 1 © 2017

Architettura degli Elaboratori

Sistema esadecimale 7

• b=16

• Possibili cifre: {0;1;2;3;4;5;6;7;8;9;A;B;C;D;E;F} 40

2

= · 16 +

7B9.1 7

16 · 16 +

11

+

9 / 16 =

1 1977.0625

10

Una cifra esadecimale può rappresentare 4 cifre binarie:

1100 1110 1001 110011101001 = CE9

2 16

C E 9 © 2017

Architettura degli Elaboratori

Conversioni di base (1 di 4) 8

• Da ottale/esadecimale a binario: 40

espansione di ogni cifra in una terna/quaterna di

cifre binarie.

• Da binario a ottale/esadecimale:

raggruppamento in terne/quaterne di cifre e

sostituzione di ciascuna terna/quaterna con

l’opportuna cifra ottale/esadecimale.

• Da qualsiasi base a decimale:

applicando la definizione di notazione posizionale.

© 2017

Architettura degli Elaboratori

Conversioni di base (2 di 4) 9

Da decimale a qualsiasi altra base b

si prendono i resti

Parte intera: 40

delle divisioni successive per b

Esempio: 2009 = 7D9

10 16

2009/16 = 125 resto: 9

125/16 = 7 resto: 13=D L’ultima cifra

16 è la più

7/16 = 0 resto: 7 significativa

Il procedimento si arresta © 2017

Architettura degli Elaboratori

Conversioni di base (3 di 4) 10

Da decimale a qualsiasi altra base b

si prendono le parti intere

Parte frazionaria: 40

delle moltiplicazioni successive per b

Esempio: 0.6875 = 0.1011

10 2

0.6875·2 = 1.375 parte intera: 1 La prima cifra

0.375·2 = 0.75 parte intera: 0 è la più

significativa

0.75·2 = 1.5 parte intera: 1

0.5·2 = 1 parte intera: 1

Il procedimento si arresta © 2017

Architettura degli Elaboratori

Conversioni di base (4 di 4) 11

Da decimale a qualsiasi altra base b

Parte frazionaria 40

Il procedimento può anche essere infinito!

= 0. …

Esempio: 0.3 01001

10 2

0.3·2 = 0.6 parte intera: 0

0.6·2 = 1.2 parte intera: 1

0.2·2 = 0.4 parte intera: 0

0.4·2 = 0.8 parte intera: 0

0.8·2 = 1.6 parte intera: 1

0.6·2 = 1.2 parte intera: 1

… … … © 2017

Architettura degli Elaboratori

Rappresentazione negli elaboratori 12

Negli elaboratori, l’elemento base

per la rappresentazione delle 40

informazioni è il BInary digiT o più

semplicemente BIT (Tukey, 1947).

Può essere realizzato in molti modi

diversi (carica elettrica, campo

magnetico, ecc.), ma in tutti i casi può

assumere esattamente 2 valori e

corrisponde quindi a una cifra binaria.

Qualsiasi informazione in un

elaboratore è rappresentata tramite un

numero finito di bit. © 2017

Architettura degli Elaboratori

Rappresentazione finita: osservazione 13

Utilizzando un numero di cifre finito si può

rappresentare solo una quantità finita di numeri. 40

Esempio per i numeri naturali:

base n. di cifre quantità min max

M M

10 M 10 0 10 -1

4

10 4 10 0 9999

M M

0 2 -1

2 M 2 4

2 4 2 0 15

10

2 10 2 0 1023

20

2 20 2 0 1048575

30

2 30 2 0 1073741823 © 2017

Architettura degli Elaboratori

Potenze di 2 14

Quando il numero di bit è elevato, si usano delle

abbreviazioni analoghe a quelle delle unità di misura 40

Prefisso Nome Pot. di 2 Valore

10

1Ki

1K kibi-

kilo- 2 1.024

20

1Mi

1M mega-

mebi- 2 1.048.576

30 1.073.741.824

1Gi gibi-

1G giga- 2 40 12

1T tera- 2 ~1.1 x 10

1Ti tebi-

IEC

60027 50 15

1P peta- 2 ~1.1 x 10

1Pi pebi- 60 18

1Ei

1E exbi-

exa- 2 ~1.2 x 10

70 21

1Z zeta- 2 ~1.2 x 10

1Zi zebi- 80 24

1Y yotta- 2 ~1.2 x 10

1Yi yobi- © 2017

Architettura degli Elaboratori

Numeri naturali 15

Esempio di rappresentazione con M=4 cifre (bit): 40

0000 = 0

2 10

0001 = 1

2 10

0010 = 2

2 10

0011 = 3

2 10

0100 = 4

2 10

1110 = 14

2 10

1111 = 15

2 10

I numeri maggiori di 15 non sono rappresentabili. © 2017

Architettura degli Elaboratori

Numeri interi: ampiezza e segno 16

Il primo bit (quello più significativo) viene utilizzato

per indicare il segno: 40

1111 -7

«

2 10

1110 -6

«

2 10

1101 -5

«

2 10

1001 -1

«

2 10

1000 -0

«

2 rappresentazioni 2 10

dello 0 0000 = +0

10

2

0001 = +1

2 10 Si riduce il numero

… di interi positivi

rappresentabili

0110 = +6

2 10

0111 = +7

2 10 © 2017

Architettura degli Elaboratori

Numeri interi: eccesso P 17

Il valore rappresentato si ottiene sottraendo P

al valore calcolato secondo la notazione posizionale. 40

M-1

Esempio con M=4 e P=8 (di solito P=2 ):

0000 -8 = 0 -8

«

2 10 10 10

0001 -7 = 1 -8

«

Dissimmetria 2 10 10 10

0010 -6 = 2 -8

«

2 10 10 10

… -1

0111 «

2 10 Una sola

1000 0 rappresentazione

«

2 10 dello 0

1001 1

«

2 10

1110 6

«

2 10

1111 7

«

2 10 © 2017

Architettura degli Elaboratori

Numeri interi: complemento a 1 18

La rappresentazione di un intero positivo coincide con

quella del corrispondente numero naturale. 40

La rappresentazione di un intero negativo si ottiene

complementando bit a bit quella del suo opposto.

1000 -7

«

2 10

1001 -6

«

2 10

1110 -1

«

2 10

1111 -0

«

2 rappresentazioni 2 10

dello 0 0000 = +0

2 10

0001 = +1

2 10

0110 = +6

2 10

0111 = +7

2 10 © 2017

Architettura degli Elaboratori

Numeri interi: complemento a 2 19

La rappresentazione di un intero positivo coincide con

quella del corrispondente numero naturale. 40

La rappresentazione di un intero negativo si ottiene

aggiungendo una unità al complemento a 1.

1000 -8

«

2 10

1001 -7

«

2 10

1111 -1

«

2 10

0000 = 0

2 10

0001 = +1

2 10

= +6

0110

2 10

0111 = +7

2 10 © 2017

Architettura degli Elaboratori

Complemento a 2: proprietà 20

È il metodo di rappresentazione più diffuso, perché è

l’unico tra quelli visti con le seguenti proprietà.

tutte 40

• Ha una sola rappresentazione dello 0.

• Ha una aggiungendo 1 al massimo

struttura ciclica:

numero rappresentabile si ottiene il minimo numero

rappresentabile.

• Consente le operazioni aritmetiche con i numeri

negativi usando le valide per i numeri

stesse regole

positivi. Esempi: 0011 +3 0011 +3

0100 +4 1100 -4

0111 +7 1111 -1 © 2017

Architettura degli Elaboratori

Complemento a 2: overflow 21

Nell’eseguire le operazioni aritmetiche, ci si deve

comunque assicurare che il risultato sia 40

rappresentabile con il numero di bit a disposizione.

Se ciò non è vero (overflow), l’esito dell’operazione è

privo di significato.

Come riconoscere l’overflow? Tramite i riporti.

Riporto nel bit Riporto “nel bit a Esito

di segno SX del segno” dell’operazione

No No OK (-)

No Si OVERFLOW

Si No (+)

OVERFLOW

Si Si OK © 2017

Architettura degli Elaboratori

Overflow: esempi 22

0101 +5 Rip. bit segno Rip. SX bit segno Esito

+2 No No OK

0010 40

0111 +7

1011 -5 Rip. bit segno Rip. SX bit segno Esito

-6 No Si OVERFLOW

1010

1¬0101 -11

0011 +3 Rip. bit segno Rip. SX bit segno Esito

+6 Si No OVERFLOW

0110

1001 +9

1011 -5 Rip. bit segno Rip. SX bit segno Esito

1110 -2 Si Si OK

1¬1001 -7 © 2017

Architettura degli Elaboratori

Numeri non interi (1 di 2) 23

FIXED-POINT R = I.F 40

parte intera; parte frazionaria

I: F:

Il numero di bit riservati a I e a F non dipende

da R: il decimale

punto è fisso.

A seconda delle applicazioni, la posizione del punto

decimale può essere codificata o implicita.

cifre frazionarie può essere

Nota: un numero con N F N

trattato come un intero se viene moltiplicato per 2 F © 2017

Architettura degli Elaboratori

Numeri non interi (2 di 2) 24

FLOATING-POINT (standard IEEE 754) 40

E

R = M·2

31 30 23 22 0

¯¯ ¯¯ ¯

e m

s

1 8 bit 23 bit

M = {s }1.m

E = e - 127 © 2017

Architettura degli Elaboratori

Rappresentazione floating-point 25

Standard IEEE 754 40

E

R = M·2

M (mantissa) 24 bit: 1 per il segno s (0=“+”)

Þ 23 per l’ampiezza

1.xxx…xx - in notazione fixed point normalizzata;

1) non viene rappresentata,

la parte intera (sempre

i 23 bit rappresentano la parte frazionaria m = xxx…xx e

E (caratteristica) 8 bit: in notazione eccesso 127( )

Þ © 2017

Architettura degli Elaboratori

Rappresentazione floating-point: esempio 26

Standard IEEE 754 40

E

R = M·2 -2

Es: 0.3 = 0.01001 = 1.0011 ·2

10 2 2

M = +1.0011 s = 0 m = 0011

E = -2 = e-127 e = 125 = 01111101

10 2

31 30 23 22 0

¯ ¯ ¯¯ ¯

0 01111101 00110011001100110011001

1 8 bit 23 bit

In esadecimale: 3E999999 © 2017

Architettura degli Elaboratori

Numeri f.p. rappresentabili 27

E

R = M·2

31 30 23 22 0 40

¯¯ ¯¯ ¯

e m

s

1 8 bit 23 bit £ £

Intervallo dei numeri rappresentabili -23

1 |M| 2-2

£ £

M = {s }1.m 1.00…0 |M| 1.11…1

2 2 £ £

-126 E 127

£255 Þ £+128

e

E = e – 127 0£ -127£ E

i valori estremi sono riservati per situazioni particolari:

Þ

e m

= 0 il numero 0 (se = 0)

¹

m 0) numero non normalizzato

(se Þ ¥

e m

= 255 il numero (se = 0)

¹

m

(se 0) numero non valido © 2017

Architettura degli Elaboratori

Numeri f.p. rappresentabili 28

E

R = M·2 40

-23

1 |M| 2-2 -126 E 127

£ £ £ £

il numero P con modulo più piccolo ( 0):

¹ -38

P 1.18 ·10

-126

= 1·2 ≈ 10

(con mantissa normalizzata)

-149 -45

P 2 1.4 ·10

-126

= 0.0…01·2 = ≈ 10

(non normalizzato)

il numero G con modulo più grande: +38

G ·2 3.4 ·10

-23 +127

= (2 - 2 ) ≈ 10 © 2017

Architettura degli Elaboratori

Numeri f.p. rappresentabili 29

E

R = M·2

Intervallo dei numeri rappresentabili sull’asse reale: 40

R

-G -P P G

· 0

d -45 +38

P ≈ 1.4 ·10 G ≈ 3.4 ·10

10 10

degli infiniti numeri reali compresi tra - G e G sono

32 9

rappresentabili con esattezza solo (≈4·10 ) numeri

2

razionali (in realtà un po’ meno); in generale un numero

reale sarà rappresentato dal più vicino di questi

R

numeri razionali; l’errore di approssimazione è d/2

£

err ≤ d/2

a © 2017

Architettura degli Elaboratori

Numeri f.p. rappresentabili 30

E

R = M·2

Intervallo dei numeri rappresentabili sull’asse reale: 40

R

-G -P P G

· 0

d -45 +38

P ≈ 1.4 ·10 G ≈ 3.4 ·10

10 10

è la differenza tra due numeri rappresentabili

d

consecutivi: E

1.xx…x1·2

E

-1.xx…x0·2 E E-23

d=0.00…01·2 = 2 E-24

err ≤ d/2 = 2

a © 2017

Architettura degli Elaboratori

Errori nella rappresentazione f.p. 31

E

R = M·2

Intervallo dei numeri rappresentabili sull’asse reale: 40

-P P G

-G 0

E-24 -45 +38

err ≤d/2=2 P ≈ 1.4 ·10 G ≈ 3.4 ·10

a 10 10

l’errore assoluto di approssimazione è funzione di E:

err

a

-126-24

err è piccolo vicino allo 0 (2 )

▪ a +127-24

err è grande vicino a G (2 )

▪ ±

a err

Ma ciò che più interessa è l’errore relativo :

r

E-24 -24

err 2 2

a

err = = = (1 M<2)

£

r E

R M·2 M

-24 -8

err 2 ≈ 10

£

r © 2017

Architettura degli Elaboratori

Caratteristiche della rappresentazione f.p. 32

E

R = M·2

Intervallo dei numeri rappresentabili sull’asse reale: 40

-P P G

-G 0

-24 -8 -45 +38

err 2 ≈ 10 P ≈ 1.4 ·10 G ≈ 3.4 ·10

£

r 10 10

precisione: ≈ 7 decimali significativi (es: h=173.4768 cm)

Esempi di grandezze fisiche “estreme” i cui valori sono

“gestibili” con questa rappresentazione f.p.:

27

▪ distanza terra - quasar: 10 m

»

-18

▪ dimensione quark: 10 m

» © 2017

Architettura degli Elaboratori

Caratteristiche della rappresentazione f.p. 33

E

FLOATING POINT (standard IEEE 754) R = M·2 40

PRECISIONE DOPPIA: 64 bit

63 62 52 51 0

¯¯ ¯¯ ¯

e m

s

1 11 bit 52 bit

M = {s }1.m

E = e - 1023 © 2017

Architettura degli Elaboratori

Rappresentazione f.p. in precisione doppia 34

E

R = M·2

PRECISIONE DOPPIA: 64 bit 40

-P P G

-G 0

-17 -308 +308

err ≈ 10 P ≈ 2.2 ·10 G ≈ 1.8 ·10

r 10 10

precisione: ≈ 16 cifre decimali significative.

64 18

Sono rappresentabili solo 2 = 16 E (EXA = 10 ) degli

infiniti numeri reali compresi tra -G e G.

Esempio di grandezza fisica estrema gestibile con questa

rappresentazione f.p.: 80

▪ numero di particelle subatomiche nell’universo: ≈ 10 © 2017

Architettura degli Elaboratori Esercizi 35

1. convertire 25493 a binario (16 bit) e ad esadecimale;

10

2. eseguire la conversione inversa;

a binario (16 bit) in virgola fissa (8 bit per la parte intera, 8 per quella

3. convertire 12.6 10 40

frazionaria);

4. convertire 56 a binario (prima a 8 bit e poi a 16 bit);

10 a binario in complemento a 2 (prima a 8 bit e poi a 16 bit);

5. convertire -56 10 (binario a 8 bit) fornisce +56 (binario a 8

6. constatare che il complemento a 2 di -56 10 10

bit);

7. trovare la codifica floating-point su 32 bit (standard IEEE 754) di 12.6 ed esprimerla

10

in notazione esadecimale;

8. trovare la codifica floating-point del numero reale rappresentabile immediatamente

successivo a quello dell’esercizio precedente e calcolare la distanza (differenza) tra i

due;

9. sia 7F700000 la notazione esadecimale che rappresenta la codifica floating-point

E

(standard IEEE 754) di un numero reale; esprimerne il valore nelle 2 forme: M´2 e

Y

X´10 ;

10. rifare l’esercizio precedente partendo da 80FFFFFF;

11. eseguire l’operazione di addizione tra i due numeri floating-point precedenti e scrivere

la codifica floating-point esadecimale del risultato: valutare e commentare l’errore

commesso. © 2017

Architettura degli Elaboratori Soluzioni (1 e 2) 36

1. convertire 25493 a binario (16 bit) e ad esadecimale:

10

bisogna dividere per due considerando quoziente e resto

25493 | 1 ← resto 40

quoziente → 12746 | 0

6373 | 1

3186 | 0

1593 | 1

796 | 0

398 | 0

199 | 1

99 | 1

49 | 1

24 | 0

12 | 0

6 | 0

3 | 1

1 | 1 ↑

25493 = 1100011100101012 = 0110.0011.1001.01012 =639516

10

2. eseguire la conversione inversa:

3 2 1 0 25493

6 * 16 3 * 16 9 * 16 5 * 16

+ + + = 10 © 2017

Architettura degli Elaboratori

Soluzioni (3, 4 e 5) 37

3. convertire 12.6 a binario (16 bit) in virgola fissa (8 bit per la parte intera, 8 per

10

quella frazionaria):

= 12 + 0.6

12.6 10 40

• conversione della parte intera rappresentata con 8 bit: 12 = 00001100

10 2

• conversione della parte frazionaria con 8 bit: 0.6 = 10011001 (parte

10 2

frazionaria periodica)

= 00001100.10011001

in definitiva 12.6 10 2

4. convertire 56 a binario (prima a 8 bit e poi a 16 bit);

10

= 00111000 con otto bit; 56 = 0000000000111000 con sedici bit

56 10 2 10 2

5. convertire -56 a binario in complemento a 2 (prima a 8 bit e poi a 16 bit):

10 è 001110002 (il bit più a sinistra rappresenta il

la rappresentazione con 8 bit di +56 10

segno +); per convertire -56 basta complementare tutti i bit della rappresentazione

10

di +56 ed aggiungere 1 al bit meno significativo:

10 +

11000111 2

1 2

--------------------

11001000 2

+56 con 16 bit: 0000000000111000 (il bit più a sinistra rappresenta il segno +)

10

-56 con 16 bit: 1111111111001000 (il bit più a sinistra rappresenta il segno -)

10 © 2017

Architettura degli Elaboratori Soluzioni (6 e 7) 38

6. constatare che il complemento a 2 di -56 (binario a 8 bit) fornisce +56 :

10 10

+ (complementazione dei bit che rappresentano -56 )

00110111 2 10

1 2 40

-----------------

00111000 cioè +56

2 10

7. trovare la codifica floating-point su 32 bit (standard IEEE 754) di 12.6 ed

10

esprimerla in notazione esadecimale:

____

= 1100,1001 ____

12.6 10 2

• bisogna normalizzare la mantissa: 1.1001001 * 2³; quindi E=3

2

• segno è +; quindi il bit 31 della codifica deve essere posto a 0

• codifica degli 8 bit relativi all’esponente e:

= E +127 quindi = 3+127 =130; in binario = 10000010

e e e 2

• per quando riguarda la parte frazionaria della mantissa, bisogna ricordare che essa

m

è periodica per cui nei 23 bit riservati si inserisce, partendo da sinistra verso destra, la

parte non periodica della mantissa, poi la parte periodica, quest’ultima replicata fino al

riempimento di tutti i bit a disposizione; quindi:

= 10010011001100110011001

m

in definitiva: 0_10000010_10010011001100110011001

in esadecimale: 0100.0001.0100.1001.1001.1001.1001.1001

4 1 4 9 9 9 9 9

4149999916 © 2017

Architettura degli Elaboratori

Soluzioni (8, 9 e 10) 39

8. trovare la codifica floating-point del numero reale rappresentabile immediatamente

successivo a quello dell’esercizio precedente e calcolare la distanza tra i due:

d

codifica floating-point del numero reale rappresentabile immediatamente successivo:

01000001010010011001100110011010 40

(si è aggiunto 1 al bit meno significativo della mantissa).

-23 3 -20

= 0.00000000000000000000001*2³ = 2 * 2 = 2

d

9. sia 7F700000 la notazione esadecimale che rappresenta la codifica floating-point E

(standard IEEE 754) di un numero reale N1; esprimerne il valore nelle 2 forme: M 2 e

´

Y

X 10 :

´ 7 F 7 0 0 0 0 0

0111.1111.0111.0000.0000.0000.0000.0000

s = + (bit 31 = 0 )

2

e = 11111110 = 254; E = e – 127 cioè E = 254-127 =127

127

N1 = 1.1110 * 2

38

N1 3.19 * 10

@

10. rifare l’esercizio precedente per il numero reale N2 rappresentato da 80FFFFFF:

8 0 F F F F F F

1000.0000.1111.1111.1111.1111.1111.1111

s = - (bit 31 a 1 )

e = 00000001 = 1; E = e – 127 cioè 1-127 = -126

2 -126

N2 = - 1.11..11 * 2

-38

N2 1.76 * 10

@ © 2017

Architettura degli Elaboratori Soluzioni (11) 40

11. eseguire l’operazione di addizione tra i due numeri floating-point precedenti e

scrivere la codifica floating-point esadecimale del risultato: valutare e

commentare l’errore commesso: 40

127 -126

i numeri sono: N1 = 1.1110 * 2 e N2 = - 1.11..11 * 2

prima di eseguire l’operazione, bisogna confrontare gli esponenti e portare il più

piccolo (-126) allo stesso valore del più grande (+127), spostando di 253 posizioni

verso sinistra il punto di radice di N2: 127

N2 = 0.000………………………………………………………..………0001111… * 2

127 127

N1+N2 = 1.1110 * 2 +0.000……………………...…………..………0001111… * 2

si osserva che con questa operazione vengono perse le cifre più significative della

mantissa di N2; infatti i 23 bit che la rappresentano risultano tutti zero per cui, quando

127

si esegue l’operazione N1 + N2, il valore del risultato rimane quello di N1=1.1110 * 2

e la codifica esadecimale del risultato è la stessa di N1: 7F700000 (in sostanza si è

cercato di sommare ad N1 un valore che è inferiore alla sua “distanza” dal numero

rappresentabile immediatamente più grande). © 2017

Architettura degli Elaboratori Fine

-1.g Rappresentazione delle informazioni

Rappresentazione binaria

delle informazioni numeriche

NUMERI NATURALI

32 32

con 32 bit (i primi 2 = 4G numeri) (da 0 a 2 -1)

31

00 … 00 2 10 ... 00

0 31

1 00 ... 01 2 +1 10 ... 01

31

2 00 ... 10 2 +2 10 ... 10

… … … …

… … … …

… … … …

31 32

2 -2 01 ... 10 2 -2 11 ... 10

31 32

2 -1 01 ... 11 2 -1 11 ... 11

Rappresentazione binaria

delle informazioni numeriche

NUMERI NATURALI

32 32

con 32 bit (i primi 2 = 4G numeri) (da 0 a 2 -1)

31

00 … 00 2 10 ... 00

0 31

1 00 ... 01 2 +1 10 ... 01

31

2 00 ... 10 2 +2 10 ... 10

… … … …

… … … …

… … … …

31 32

2 -2 01 ... 10 2 -2 11 ... 10 +1

31 32

2 -1 01 ... 11 2 -1 11 ... 11

100 ... 00

Rappresentazione binaria

delle informazioni numeriche

NUMERI NATURALI

32 32

con 32 bit (i primi 2 = 4G numeri) (da 0 a 2 -1)

"

0 00 … 00 01 ... 11 10 ... 00

½½

1 00 ... 01

… …

31

2 -2 01 ... 10 _ _

31 0010 … 00 1100 ... 00

2 -1 01 ... 11

31

2 10 ... 00

31

2 +1 10 ... 01

… … ½½ 11 ... 11

00 ... 00

32

2 -2 11 ... 10 "

32

2 -1 11 … 11

" = “guardalinee”

bit C

Rappresentazione binaria

delle informazioni numeriche

NUMERI NATURALI INTERI

®

8

con 8 bit (2 = 256 numeri) (da -127 a +128)

ECCESSO 127 negativi positivi

1

-127 00000000 128 10000000

0 Ü

Ü 2

-126 1 00000001 129 10000001

3

2 00000010 130 10000010

-125 …

… … … … …

… … … …

… …

… … … … …

127

-1 126 01111110 254 11111110

128

0 127 01111111 255 11111111

Rappresentazione binaria

delle informazioni numeriche

NUMERI NATURALI INTERI

®

8

con 8 bit (2 = 256 numeri) (da -128 a +127)

COMPLEMENTO A DUE positivi negativi

-128 10000000

0 00000000 128

0 Ü

Ü -127

1 1 00000001 129 10000001

2 00000010 130 10000010

-126

2 … … … …

… …

… … … …

… …

… … … …

… -2

126 126 01111110 254 11111110 +1

-1

127 127 01111111 255 11111111

100000000

Rappresentazione binaria

delle informazioni numeriche

NUMERI NATURALI INTERI

®

con 32 bit

positivi negativi

31 31

00 … 00 2 10 ... 00 -2

0 31

31 -2 +1

1 00 ... 01 2 +1 10 ... 01 31

31 -2 +2

2 00 ... 10 2 +2 10 ... 10 …

… … … …

… … … … …

… … … … …

31 32 -2

2 -2 01 ... 10 2 -2 11 ... 10

31 32 -1

2 -1 01 ... 11 2 -1 11 ... 11

Rappresentazione binaria

delle informazioni numeriche

NUMERI INTERI 31 31

con 32 bit (da -2 a + 2 -1)

COMPLEMENTO A DUE

positivi negativi

31

00 … 00 -2 10 ... 00

0 31

-2 +1 10 ... 01

1 00 ... 01 31

-2 +2 10 ... 10

2 00 ... 10

… … … …

… … … …

… … … …

31 -2 11 ... 10

2 -2 01 ... 10 +1

31 -1 11 ... 11

2 -1 01 ... 11 100 ... 00

Rappresentazione binaria

delle informazioni numeriche

NUMERI INTERI (complemento a 2)

31 31

con 32 bit (da -2 a + 2 -1)

" " bit = “guardalinee”

V

31

-2 10 ... 00 01 ... 11 10 ... 00

½½

31

-2 +1 10 ... 01

… …

-2 11 ... 10 _ _

0010 … 00 1100 ... 00

-1 11 … 11

0 00 … 00

1 00 ... 01

… … ½½

00 ... 00 11 ... 11

31

2 -2 01 ... 10

31

2 -1 01 ... 11

"

Rappresentazione binaria

delle informazioni numeriche

NUMERI INTERI (complemento a 2)

con 32 bit 31

31 Il bit più significativo ha “peso” negativo (-2 )

10 ... 00

-2 ¬ 0

Gli altri bit hanno “peso” positivo (+2 )

31

-2 +1 10 ... 01 ¬ 1 )

31

-2 +2 10 ... 10 (+2

¬

… … i

)

… … (+2

¬

0 00 … 00

1 00 ... 01

… …

31

2 -2 01 ... 10

31

2 -1 01 ... 11

Rappresentazione binaria

delle informazioni numeriche

NUMERI INTERI (complemento a 2)

Come passare dalla notazione: con P bit

con N bit a quella

C C … C C C … C C

C C … C C Þ P-1 P-2 N N-1 N-2 1 0

N-1 N-2 1 0

{0 1}

C

• = ,

i

• P > N

Rappresentazione binaria

delle informazioni numeriche

“PESO” DEGLI N BIT

NEL COMPLEMENTO A DUE

( {0 1})

C C … C C C = ,

i

N-1 N-2 1 0

= C C … C C

N-1 N-2 1 0

) + + + +

·(-2 ·2 ·2 ·2

N-1 N-2 1 0

=

C 0

• se il numero è positivo

N-1 =

C 1

• se il numero è negativo

N-1

vediamo separatamente i due casi …

Rappresentazione binaria

delle informazioni numeriche

con N bit: 0C …C C

• caso dei numeri positivi (C = 0)

N-1 N-2 1 0

= 0 C … C C

N-1 N-2 1 0

(-2 )+ 2 + + 2 + 2 {1}

· · · ·

N-2 1 0

aggiungendo (P - N) termini nulli alla {1}, il valore non cambia:

= 0 0 … 0 C … C C

P-1 P-2 N-1 N-2 1 0

(-2 )+ 2 + + 2 + 2 + + 2 + 2

· · · · · ·

N-2 1 0

con P bit: 000…0C … C C

notazione posizionale N-2 1 0

Rappresentazione binaria

delle informazioni numeriche

con N bit: C …C C

• caso dei numeri negativi (C = 1) 1

N-1 N-2 1 0

= C … C C

N-1 N-2 1 0

1·(-2 )+ ·2 + + ·2 + ·2 {1}

N-2 1 0

11…111… +

1

= 100…000… (P > N)

P-1 P-2 P-3 N+1 N N-1 N-1

2 = 2 +2 +…+2 +2 +2 +2

P-1 P-2 P-3 N+1 N N-1 N-1

-2 +2 +2 +…+2 +2 +2 +2 = 0

aggiungendo questa somma (= 0) alla {1}, il valore non cambia:

= C … C C

P-1 P-2 P-3 N-1 N-2 1 0

-2 +2 +2 +…+ 2 + ·2 + + ·2 + ·2

N-2 1 0

con P bit: 111…11C … C C

notazione posizionale N-2 1 0

Rappresentazione binaria

delle informazioni numeriche

NUMERI INTERI (complemento a 2)

Per passare dalla notazione: con P bit

a quella

con N bit S S … S C C … C C

S C … C C Þ N-1 N-2 1 0

N-2 1 0

si estende verso sinistra il bit di segno

Testo di rif.to:

[Congiu] - 1.2 (pg. 17–22)

Rappresentazione delle informazioni

-1.h Testi

Immagini

Suoni

Video

Testi: lo standard ASCII 1

American Standard Code for Information Interchange 18

7

7 bit, 2 = simboli diversi:

128

• (a… z A…Z 0 … 9 ! ? , . ; : @ # $ …)

• alcuni codici di controllo, per controllare la

visualizzazione di un testo (capo riga, salto di pagina, …)

o la sua trasmissione (XON, XOFF, …)

I 7 bit sono memorizzati e trasmessi in un byte.

Il bit in più può essere usato come bit di parità per

rilevare eventuali errori di trasmissione. © 2017

Architettura degli Elaboratori

Tabella dei caratteri ASCII 2

Da un documento del 1972… 18

© 2017

Architettura degli Elaboratori

Tabella dei caratteri ASCII 3

18

© 2017

Architettura degli Elaboratori

Oltre lo standard ASCII 4

• Codifica ASCII estesa

● 256 simboli; i 128 aggiuntivi rappresentano caratteri

di alfabeti nazionali (à, è, ô, …) e altro (½, …) 18

ƒ, ®,

● Sviluppate varie estensioni tra loro incompatibili

• (a 8 bit): 16 tabelle,

Standard ISO/IEC 8859

compatibili ASCII, per soddisfare le esigenze di

altrettanti gruppi di lingue nazionali (occidentali).

compatibile con ISO/IEC 8859:

• Standard UNICODE

UTF-8 (a 8 bit),

• 16

UTF-16 (a 16 bit): 2 = 65536 simboli per

• rappresentare i caratteri di quasi tutte le principali

lingue scritte del mondo (non alcune lingue orientali);

32 = 4G (testi multilingue,

UTF-32 (a 32 bit): 2

• comprese tutte le orientali e quelle estinte). © 2017

Architettura degli Elaboratori

Codifica ASCII estesa (8 bit) 5

128 simboli in più (DOS CodePage 850) 18

© 2017

Architettura degli Elaboratori

Codifica ASCII estesa (8 bit) 6

Esempio di estensione della codifica ASCII 18

ISO Latin 1 (da 160 a 255)

(i codici dal 128-159 sono riservati per funzioni di controllo)

© 2017

Architettura degli Elaboratori

Rappresentazione di stringhe in memoria 7

indirizzo contenuto direttive simboliche assembly

00000000 51756573 .ASCII "Questa è una prova" 18

746120E8

20756E61

2070726F

7661

00000012 00 .byte 0 @ fine stringa

.DATA

00000000 41424344 .ASCII "ABCDabcd"

61626364

00000008 00 .byte 0 @ fine stringa

00000009 45464748 .ASCII "EFGHefgh"

65666768

00000011 00 .byte 0 @ fine stringa

00000012 31323334 .ASCII "12345678"

35363738

0000001a 00 .byte 0 @ fine stringa...

© 2017

Architettura degli Elaboratori

Immagini: rappresentazione raster 8

rastrum

Dal latino (“rastrello”): sottolinea come

l’immagine sia costituita da una griglia di punti. 18

I punti sono detti pixel (“PICture Elements”).

Il numero di bit usati per rappresentare un pixel

definisce il tipo di immagine

• 1 bit/pixel: bianco e nero

• 8 bit/pixel: scala di grigi, a colori con palette

• 24 bit/pixel: 16’777’216 colori (“true color”)

Esempi di standard:

• BMP

• PNG

• JPEG Formato compresso (vediamo che significa) © 2017

Architettura degli Elaboratori

Rappresentazione raster: dimensioni 9

La qualità di un’immagine raster aumenta con il numero

di pixel che la compongono 18

Anche l’occupazione in byte, però, aumenta!

900 KiB

• Immagine 640x480, 24 bit/pixel:

• Immagine 3648x2736, 24 bit/pixel: 29241 KiB (32x)

Per ovviare al fenomeno si adotta la compressione © 2017

Architettura degli Elaboratori

Compressione: lossless vs. lossy 10

• (lossless)

Compressione senza perdite 18

Preserva interamente l’informazione originaria

● Fattore di compressione: 2 (tipico)

● Esempi: PNG (immagini), ZIP (documenti generici)

• (lossy)

Compressione con perdita

Scarta alcune informazioni, valutate meno rilevanti

● Il documento originale non può essere ricostruito

● fedelmente.

Fattore di compressione: 20 o più

● Esempi: JPEG (immagini), MP3 (suoni)

● © 2017

Architettura degli Elaboratori

Compressione lossy: esempio (JPEG) 11

bmp 18

La nascita di Venere.Botticelli.bmp (non compressa: 2.59 Mbyte) © 2017

Architettura degli Elaboratori

Compressione lossy: esempio (JPEG) 12

jpg 18

La nascita di Venere.Botticelli.jpg (compressa: 221 Kbyte)

.jpg (221 KB): compression factor = 11.7

.bmp (2.59 MB) Þ © 2017

Architettura degli Elaboratori

Immagini: rappresentazione vettoriale 13

Insieme di elementi geometrici bidimensionali

(punti, linee, archi di curva, triangoli…) o 18

tridimensionali (cubi, quadriche, …)

...

/V /v ldef

/y {_r 2 copy curveto} bdef

/Y /y ldef

/l {_r lineto} bdef

Esempi di standard: /L /l ldef

/m {_r moveto} bdef

% path construction operators

• Postscript (immagini 2D) /_R {.25 sub round .25 add} bdef

...

• DXF (disegno tecnico)

• RISpec (immagini 3D)

• TrueType (caratteri) © 2017

Architettura degli Elaboratori

Suoni: rappresentazione (1 di 2) 14

1. Il suono (vibrazione dell’aria) tramite un trasduttore

(microfono) viene trasformato in un segnale 18

(tensione elettrica che varia nel

elettrico analogico

tempo in modo al suono)

analogo

2. Tramite un convertitore analogico/digitale (A/D)

il segnale analogico viene discretizzato

• nel TEMPO, raccogliendone campioni

a una frequenza prestabilita

• in AMPIEZZA, codificando ciascun A/D

campione con un numero finito di bit

La sequenza dei campioni codificati

è la rappresentazione digitale del suono. © 2017

Architettura degli Elaboratori

Suoni: rappresentazione (2 di 2) 15

Il segnale sonoro può essere ricostruito con la

trasformazione inversa 18

D/A suono

segnale elettrico trasduttore

valori digitali

La rappresentazione è tanto più fedele quanto maggiori

sono

•la frequenza di campionamento

(per riprodurre fedelmente un suono a frequenza f

bisogna campionare a frequenza almeno 2 )

f

•il (rapp. segnale/rumore)

numero N di bit dei campioni © 2017

Architettura degli Elaboratori

Esempio: il Compact Disc (1982) 16

Frequenza di campionamento: 44100 Hz

(la massima frequenza udibile è ~20KHz). 18

16 bit per campione.

Suono stereofonico: 2 canali.

Un brano audio di 3 minuti occupa ~31’000 KiB!

Anche per i suoni è importante la compressione.

Esempio: 3 minuti di suono compresso (lossy)

in MP3 a 128 Kbit/s occupano ~3’000 KiB. © 2017

Architettura degli Elaboratori

Video 17

Un video è una sequenza di immagini (“frame”)

•Cinema: 24 frame al secondo (fps) 18

•TV, standard europeo PAL: 25 fps

•TV standard USA NTSC: 30 fps

Senza compressione:

•Un minuto di video alla risoluzione di 640x480

(true color, 24fps) occupa 1’296’000 KiB (~1.2 GiB).

•Un minuto di video ad 1080p30

alta definizione

(1920x1080) occupa 10’935’000 KiB (~10.6 GiB)

La compressione è fondamentale.

Þ © 2017

Architettura degli Elaboratori

Video: compressione 18

La maggior parte dei formati sono lossy.

Vengono ereditate le tecniche per le immagini,

inoltre si effettua anche una compressione 18

lungo l’asse del tempo (predizione del moto, eccetera).

Standard più diffuso: MPEG

• DVD, digitale satellitare e terrestre

MPEG-2:

• AVC (H.264): Quicktime 7, Blu-ray Disc, …

MPEG-4

Rapporti di compressione tipici: 20 - 100

Esempi di altri formati di compressione:

(Macromedia/Adobe)

.flv: Flash Video

(DivX, Incorporated)

.divx (Microsoft)

.wmv: Windows Media Video © 2017

Architettura degli Elaboratori Fine

-1.h Rappresentazione delle informazioni

Autore mike u-1_i_RappresentazioneInfo.doc

RAPPRESENTAZIONE DELLE INFORMAZIONI NEI

CALCOLATORI

1. sistemi di numerazione (binario)

2. le informazioni numeriche:

- (senza segno - unsigned)

numeri naturali

- (con segno – signed)

numeri interi

- numeri non interi

3. le informazioni non numeriche:

- testo

- immagini

- suono

- video

08/02/18 1

Autore mike u-1_i_RappresentazioneInfo.doc

1. sistemi di numerazione

- sistema posizionale:

(… .C =

C C C C …) b

2 1 0 -1 -2

2 1 0 -1 -2

= + + + + + + = C ·b

… C ·b C ·b C ·b C ·b C ·b … S i i

2 1 0 -1 -2

i - è la base

b

- sono le cifre del numero

C i

il sistema decimale e quello binario sono due esempi di

sistemi posizionali:

- (b = 10; = {0,1,2,3,4,5,6,7,8,9})

sistema decimale: C i

Esempio: 2 1 0 -1 -2

492.17 = 4·10 + 9·10 + 2·10 + 1·10 + 7·10

10

- (b = 2; = {0,1})

sistema binario: C i

Esempio: 3 2 1 0 -1 -2

1101.01 = 1·2 + 1·2 + 0·2 + 1·2 + 0·2 + 1·2

2

08/02/18 2

Autore mike u-1_i_RappresentazioneInfo.doc

Utilizzando un numero di cifre finito si può rappresentare

solo una quantità finita di numeri:

base n. di cifre quantità min max

N N

10 N 10 0 10 -1

4

10 4 10 0 9999

N N

2 N 2 0 2 -1

4

2 4 2 0 15

10

2 10 2 0 1023

20

2 20 2 0 (1024´1024) -1

30

2 30 2 0 (1024´1024´1024) -1

Alcune potenze intere di 2 sono divenute unità di misura nel

sistema binario:

10 1024 1.024

2 1K KILO

10

20 1024 x 2 1.048.576

2 1M MEGA

20

30 1024 x 2 1.073.741.824

2 1G GIGA

30 12

40 1024 x 2 ~1.1 x 10

2 1T TERA

altre potenze intere di 2 per uso futuro:

40 15

50 1024 x 2 ~1.1 x 10

2 1P PETA

50 18

60 1024 x 2 ~1.2 x 10

2 1E EXA

60 21

70 1024 x 2 ~1.2 x 10

2 1Z ZETTA

70 24

80 1024 x 2 ~1.2 x 10

2 1Y YOTTA

08/02/18 3

Autore mike u-1_i_RappresentazioneInfo.doc

2. le informazioni numeriche

segno

segno 2. numeri interi (con – signed)

1. numeri naturali (senza - secondo la convenzione del

unsigned) “COMPLEMENTO A DUE”

caso semplice: con 4 bit

caso semplice: con 4 bit

4 4

(2 = 16 numeri, da –8 a +7)

(i primi 2 = 16 numeri, da 0 a 15)

decimale binario decimale binario

0 0000 0 0000

1 0001 1 0001

2 0010 2 0010

3 0011 3 0011

4 0100 4 0100

5 0101 5 0101

6 0110 6 0110

7 0111 7 0111

–8 1000

8 1000 –7 1001

9 1001

10 1010 –6 1010

11 1011 –5 1011

12 1100 –4 1100

13 1101 –3 1101

14 1110 –2 1110

15 1111 –1 1111

caso vero: con 32 bit caso vero: con 32 bit

32 32 32 31 31

2 =4G 0 2 –1) = 4G –2 +2 –1)

(i primi numeri, da a (2 numeri, da a

decimale binario decimale binario

0 00 … 00 0 00 … 00

1 00 ... 01 1 00 ... 01

2 00 ... 10 2 00 ... 10

… … … …

… … … …

… … … …

31

31

2 –2 01 ... 10 2 –2 01 ... 10

31

31

2 –1 01 ... 11 2 –1 01 ... 11

31

31

2 10 ... 00 –2 10 ... 00

31

31 –2 +1 10 ... 01

2 +1 10 ... 01 31

31 –2 +2 10 ... 10

2 +2 10 ... 10 … …

… … … …

… … … …

… …

32 –2 11 ... 10

2 –2 11 ... 10

32 –1 11 ... 11

2 –1 11 ... 11

08/02/18 4

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

Qualora, nel corso di una operazione aritmetica (ad es. di somma o

sottrazione) tra numeri naturali da 32 bit, il risultato superi il valore

32

massimo rappresentabile (2 –1), oppure risulti inferiore a quello

minimo (0), si ha di

ERRORE OVERFLOW.

Analogamente, qualora, nel corso di una operazione aritmetica

(ad es. di somma o sottrazione) tra numeri interi da 32 bit, il

31

risultato superi il valore massimo rappresentabile (2 –1), o

31 ), si ha di

risulti inferiore a quello minimo (–2 ERRORE

OVERFLOW. la convenzione – standard IEEE 754)

3. numeri non interi (secondo FLOATING POINT

La versione base dello standard IEEE 754 per la

rappresentazione floating point rappresenta i numeri non interi

utilizzando 32 bit, nel seguente modo. E

Il numero R si esprime nella forma: R = M 2 (notazione binaria

scientifica, analoga a quella decimale comunemente usata: es.

2

123.4 = 1.234 10 ) e viene rappresentato dalle notazioni binarie

di M (mantissa) e E (esponente).

La mantissa M è “normalizzata”, cioè è posta nella forma

M=1.xxx (la sua parte intera è sempre = 1).

M è rappresentata con 24 bit: uno per il segno e 23 per la parte

frazionaria xxx (non occorre rappresentare la parte intera in

quanto questa è sempre = 1: così si risparmia un bit).

I valori che può assumere sono pertanto compresi tra il

|M|

minimo 1.0 e il massimo 1.111 … 11 (23 bit a destra del punto

che separa la parte intera da quella frazionaria). Tenendo conto

del “peso” di questi bit, si ha quindi:

-23

1 2-2

|M|

£ £

E è un numero intero rappresentato con 8 bit secondo una

notazione particolare, detta “eccesso 127” (diversa dal

complemento a due), e può assumere i valori compresi tra –127

e +128. I valori estremi (–127 e +128) sono riservati per usi

particolari, per cui si ha: 5

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

–126 E =127

£ £

Pertanto, il modulo del numero più grande rappresentabile è pari

-23 127 +38

a: = 2-2 2 3.4 ·10

|MAX| » 10

Mentre il modulo del numero più piccolo (diverso da zero)

rappresentabile (con mantissa normalizzata) è pari a:

-126 -38

= 1 2 1.18 ·10

|MIN | »

norm 10

Con E = -127 (tutti 8 i bit uguali a 0) si ha la rappresentazione

dello zero se la mantissa è nulla, di un numero con mantissa non

normalizzata (cioè con parte intera uguale a 0) nel caso contrario

(il valore di E usato in questo caso non è –127, ma –126).

Pertanto il modulo del numero più piccolo (diverso da zero)

rappresentabile (con mantissa non normalizzata) è pari a:

-126 -23 -126 -149 -45

• •

= 0.00..01 2 = 2 2 = 2 1.4 ·10

|MIN| » 10

Con E = +128 (tutti 8 i bit uguali a 1) si ha la rappresentazione di

un valore infinito se la mantissa è nulla, di un numero non valido

(NAN – not a number) nel caso contrario.

Quando, nel corso di una operazione aritmetica tra numeri

floating point, il modulo del risultato supera il valore si ha

MAX

di quando invece è inferiore a si ha

MIN,

ERRORE OVERFLOW;

di

ERRORE UNDERFLOW

Vi sono infiniti numeri reali compresi tra questi estremi; ma i 32

bit disponibili consentono di rappresentarne, con esattezza,

32

“solo” 2 = 4 G (anzi un po’ meno perché tutte le configurazioni

con E = +128 non rappresentano numeri). Tutti gli altri potranno

essere rappresentati, in modo approssimato, utilizzando, per

ciascuno di essi, il numero rappresentabile “più vicino”. Con ciò si

commette un errore, detto di

ERRORE DISCRETIZZAZIONE

(dovuto al passaggio dal valore “continuo” dei numeri reali, con

cui si esprimono i valori delle grandezza fisiche del mondo

esterno al calcolatore, al valore “discreto” del mondo digitale

interno). che si commette con questa

L’errore assoluto e a

approssimazione non supera la metà della “distanza” tra due

d

numeri rappresentabili consecutivi (R ), che può essere

ed R

i i+1

calcolata facilmente: 6

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

E E

• •

d = R – R = 1.xxx … xx1 2 – 1.xxx … xx0 2 = 0.000 … 001

i+1 i

E -23 E E -23

• •

2 = 2 2 = 2

E -24

= d/2 = 2

e a E -24 E -24

L’errore relativo è: e = e / R = 2 / 1.xxx … xx0 2 2

» »

r a i

-8

10

In termini decimali, la precisione corrispondente a questo errore

relativo garantisce la correttezza di 7 cifre decimali significative

(quindi una parte su 10 milioni). 7

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

3. le informazioni non numeriche

RAPPRESENTAZIONE DI TESTI

Lo standard ASCII

(American Standard Code for Information Interchange):

7

7 bit, 2 = 128 simboli diversi:

- (a… z A…Z 0 … 9 ! ? , . ; : @ # $ …),

- alcuni codici di controllo, (per controllare la

visualizzazione di un testo (ad es. capo riga, salto di

pagina,…) o la sua trasmissione (ad es. XON, XOFF,…)

I 7 bit sono memorizzati e trasmessi all’interno di un byte.

Il bit in più può essere usato come bit di parità per rilevare

eventuali errori di trasmissione.

Estensione dello standard ASCII a 8 bit:

256 simboli; i 128 aggiuntivi consentono di rappresentare

caratteri di alfabeti nazionali (ad es. à, è, è, ô, , , , …).

ò

¸

Ô

Standard UNICODE (a 16 bit):

• 16

2 = 64K simboli per rappresentare i caratteri di tutte le

principali lingue scritte del mondo. 8

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

CODICI ASCII (7 BIT)

CODIFICA ASCII ESTESA (8 BIT) - DOS CodePage 850 9

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

Esistono diverse altre estensioni della codifica ASCII, che

utilizzano l’ottavo bit per rappresentare ulteriori 128 simboli,

necessari per rappresentare i diversi alfabeti nazionali.

Ad esempio:

CODIFICA ASCII ESTESA - ISO Latin 1 (da 160 a 255)

(i codici dal 128-159 sono riservati per funzioni di controllo)

WINDOWS CODE PAGE 1252 10

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

Esempio di rappresentazioni di stringhe in memoria

(linguaggio assembly ARM)

indirizzo contenuto direttive simboliche assembly

00000000 51756573 .ASCII "Questa è una prova"

746120E8

20756E61

2070726F

7661

00000012 00 .byte 0 @ fine stringa

.DATA

00000000 41424344 .ASCII "ABCDabcd"

61626364

00000008 00 .byte 0 @ fine stringa

00000009 45464748 .ASCII "EFGHefgh"

65666768

00000011 00 .byte 0 @ fine stringa

00000012 31323334 .ASCII "12345678"

35363738

0000001a 00 .byte 0 @ fine stringa... 11

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

RAPPRESENTAZIONE DI IMMAGINI

VETTORIALE:

• insieme di elementi geometrici (punti linee, cerchi,

rettangoli, archi di curva, …).

Metodo adatto per il disegno tecnico.

Programmi di tipo DRAW (es. AUTOCAD)

BIT MAP (raster):

• successione di punti, detti PIXEL (picture elements): righe

e colonne di un’area rettangolare (640x480, 1024x768,

1280x1024).

bianco e nero: un bit per punto;

a colori:

- un byte per punto (256 colori)

- 3 byte per punto (uno per colore fondamentale: RGB)

24

2 = 16M (TRUE COLOR).

I programmi che elaborano immagini bit map sono detti di

tipo PAINT (es. PAINTBRUSH)

Un’immagine bit map è di solito contenuta in un file di

estensione .bmp

Altri formati bit map talvolta usati sono: TIFF (file .tif) e

PCX (file .pcx) usato da ZSOFT Paintbrush

Un’immagine vettoriale richiede meno spazio di memoria

di una di tipo bitmap. 12

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

Immagine bit map:

- 640x480 in bianco e nero: ~38Kbyte

- 640x480 256 colori (o gray level): ~300Kbyte

- 640x480 16M colori (true color): ~900Kbyte

- 1024x768 16M colori (true color): ~2.3Mbyte

- 1280x1024 16M colori (true color): ~3.9Mbyte

Per ridurre lo spazio di memoria occupato da un

immagine bit map (e il tempo necessario per il suo

trasferimento lungo una linea di comunicazione) si

adottano comunemente tecniche di COMPRESSIONE

COMPRESSIONE LOSSLESS,

- consente di ricostruire interamente l’informazione

originaria (es. PKZIP).

- La riduzione di ingombro tipica è di circa il 50%.

- Usata per la compressione di file contenenti programmi o

dati da conservare inalterati.

- I file contenenti informazioni compresse con PKZIP sono

caratterizzati dall’estensione .zip.

- Un meccanismo di compressione lossless usato per le

immagini più semplici (256 colori), tipo cartoon, è: GIF

(file .gif).

COMPRESSIONE LOSSY,

- tollera la perdita di alcune informazioni e quindi non

consente di ricostruire fedelmente l’immagine originaria

(es. JPEG).

- Può arrivare a ridurre l’ingombro al 5%.

- Usata comunemente per memorizzare immagini a colori

(16M, true color) di tipo fotografico.

- I file contenenti immagini compresse con JPEG sono

caratterizzati dall’estensione .jpg. 13

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

RAPPRESENTAZIONE DEL SUONO

Il (andamento, nel tempo, della

segnale sonoro

• posizione di una particella d’aria che vibra), tramite un

(microfono), viene trasformato in un

trasduttore segnale

(tensione elettrica che varia, nel

elettrico analogico

tempo, in modo analogo al segnale sonoro).

Il segnale elettrico analogico, tramite un convertitore A/D

• (analogico/digitale), viene campionato (ad es. alla

frequenza di 10 KHz, cioè un campione ogni 100 e il

µs)

valore della tensione di ciascun campione viene

trasformato in un numero binario da bit; questo

N valore

viene prodotto dal convertitore A/D in un registro

digitale

accessibile al processore.

Il calcolatore provvede a leggere il valore di ciascun

• campione, prima che esso venga sostituito da quello

successivo (entro 100 nell’esempio), e costruisce,

µs,

nella sua memoria, una successione di valori digitali

che rappresenta il segnale sonoro.

Il segnale sonoro può essere ricostruito, a partire da

• questa rappresentazione interna al calcolatore,

prelevando ad uno ad uno i valori digitali, inviandoli ad un

(digitale/analogico), che opera la

convertitore D/A

conversione inversa rispetto a quella operata dall’A/D, e

inviando ad un (altoparlante) il segnale

trasduttore

elettrico analogico prodotto dal D/A.

La rappresentazione è tanto più precisa (più fedele)

• quanto maggiore è la frequenza di campionamento e

quanto maggiore è il numero di bit dei campioni.

N 14

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

Per ricostruire interamente l’informazione contenuta in un

• segnale elettrico composto da sinusoidi elementari di

frequenza non superiore a , è sufficiente campionarlo

f

MAX

con una frequenza pari almeno a .

2 f

MAX

L’orecchio umano non percepisce suoni di frequenza

• superiore a circa 20 KHz. Pertanto la rappresentazione

fedele di un brano sonoro può essere fatta

campionandolo a 44 KHz (questa è la frequenza di

campionamento usata nei CD musicali, nei quali il numero

di bit dei campioni è pari a 16)

Con questa modalità di campionamento (44 KHx, 16 bit)

• un secondo di audio occupa 44000 2 88 Kbyte; un

´ »

brano audio che duri un minuto occupa 60 88 5

´ »

Mbyte; 10 Mbyte per 2 canali (stereo).

»

L’ingombro è notevole. Per ridurlo (e per ridurre, di

• conseguenza, anche il tempo necessario per la

trasmissione del brano, ad esempio in rete) si usano

tecniche di compressione:

La compressione nel formato MP3 (file di estensione

• .mp3), recentemente affermatasi, consente di ridurre

l’ingombro di un fattore circa 5: un minuto di audio mp3

tipicamente occupa 1 Mbyte (in luogo dei 5 Mbyte

originari). Con questa riduzione risulta fattibile la

trasmissione via modem di un brano sonoro: la velocità di

trasmissione richiesta è di 20÷30 Kbyte al secondo. 15

Autore mike u-1_i_RappresentazioneInfo.docinformazioni nei calcolatori

RAPPRESENTAZIONE DEL VIDEO

Un brano video è costituito da una sequenza di immagini.

• Ad esempio, nella televisione, sono presentati 25

fotogrammi al secondo, ciascuno costituito da 576 720

´

pixel.

Per presentare sullo schermo di un calcolatore (di

• risoluzione non molto alta: 640 480 pixel) un minuto di

´

un brano video a colori (true color: 3 byte per pixel),

all’interno di una finestra che occupi solo un

trentaduesimo dello schermo, sono necessari:

640 480 (1/32) 3 25 43 Mbyte.

´ ´ ´ ´ ´60 »

Per poter gestire (memorizzare e trasmettere) un brano

• video è indispensabile ricorrere alla compressione.

Lo standard di compressione video più diffuso è MPEG

• (file di estensione .mpg), che tipicamente consente di

ridurre l’ingombro di un fattore 20, per cui un minuto di

video MPEG potrebbe occupare 2.5 Mbyte.

Altre tecniche di compressione utilizzate sono:

• AVI (file di estensione .avi), della Microsoft;

- QUICKTIME (file di estensione .mov) della Apple.

- 16

Testo di rif.to:

[Congiu] - 2.1-2.3 (pg. 27–37) Reti Logiche

00.a Porte logiche

Registri

Bus

Architettura degli Elaboratori © 2016 1

Valori logici: convenzione 2

I valori logici sono 2.

Per indicarli useremo i nomi: 26

1 0

VERO FALSO

ALTO BASSO

+5 V 0 V

I nomi in ciascuna colonna sono equivalenti.

I nomi sono solo una convenzione! © 2016

Architettura degli Elaboratori

Definizione di porta logica; porta NOT 3

Una porta logica è un dispositivo

con N ingressi ed 1 uscita, che realizza 26

un legame tra il valore presente all’uscita

e quelli presenti agli ingressi,

esprimibile con una funzione logica elementare

Primo esempio di porta logica: la porta NOT

Produce in uscita un valore logico opposto a quello

presente all’ingresso. Chiaramente N=1. © 2016

Architettura degli Elaboratori

Porte logiche AND e OR 4

La fa assumere

porta AND 26

all’uscita il valore logico 1

tutti gli ingressi

se e solo se

si trovano ad avere il valore 1

fa assumere

La porta OR

all’uscita il valore logico 1 sse

degli ingressi

ad almeno uno

è presente un valore logico 1 © 2016

Architettura degli Elaboratori

Porte logiche NAND e NOR 5

La fa assumere

porta NAND 26

all’uscita il valore logico 0

tutti gli ingressi

se e solo se

si trovano ad avere il valore 1

fa assumere

La porta NOR

all’uscita il valore logico 0 sse

degli ingressi

ad almeno uno

è presente un valore logico 1 © 2016

Architettura degli Elaboratori

Equivalenze tra porte logiche (1 di 3) 6

La funzione realizzata da una porta logica può essere

ottenuta mediante opportune sequenze di altre porte 26

logiche.

Ad esempio, le porte NOR/NAND possono essere

ottenute mediante una porta OR/AND e una NOT

collegate in sequenza © 2016

Architettura degli Elaboratori

Equivalenze tra porte logiche (2 di 3) 7

Ogni funzione logica può essere ottenuta

impiegando solo porte OR e NOT 26

Ogni funzione logica può essere ottenuta

impiegando solo porte AND e NOT © 2016

Architettura degli Elaboratori

Equivalenze tra porte logiche (3 di 3) 8

Ogni funzione logica può essere ottenuta

impiegando solo porte NAND 26

Ogni funzione logica può essere ottenuta

impiegando solo porte NOR (provarlo per esercizio) © 2016

Architettura degli Elaboratori

Tabelle di verità 9

Un secondo modo di rappresentare una rete logica è

tabella di verità,

mediante la sua 26

che specifica il valore dell’uscita per ciascuna

possibile combinazione dei valori in ingresso.

Esempi per alcune porte logiche elementari: © 2016

Architettura degli Elaboratori

OR esclusivo 10

Un esempio più complesso è dato dalla rete logica che

realizza la funzione di l’uscita Y assume

OR esclusivo: 26

il valore 1 se e solo se ai 2 ingressi sono presenti

valori logici diversi

A B Y

0 0 0

0 1 1

1 0 1

1 1 0 © 2016

Architettura degli Elaboratori

Transistor e porte logiche 11

NOT NAND NOR 26

© 2016

Architettura degli Elaboratori

Collegamenti tra porte logiche 12

NOTA: è ovvio che, mentre una stessa variabile

può essere inviata agli ingressi di diverse 26

porte logiche, non è invece lecito collegare tra

uscite di due porte logiche: se,

di loro le

infatti, una delle due imponesse alla sua uscita

un valore logico 1 e l’altra il valore 0, si

verificherebbe un conflitto (in termini di

tensioni elettriche, si verificherebbe un

“cortocircuito”, con una circolazione abnorme

di corrente e una distruzione del componente).

© 2016

Architettura degli Elaboratori

Buffer tri-state (1 di 2) 13

A 26

A controlla se in uscita

Quando A=1, Y=B “passa” il valore di B,

Quando A=0, Y=0 oppure no.

Ma Y=0 è un valore di A “passato” attraverso la porta

“aperta”, oppure è dovuto alla porta chiusa?

L’ambiguità si risolve con il buffer tri-state. © 2016

Architettura degli Elaboratori

Buffer tri-state (2 di 2) 14

Il buffer tri-state è un dispositivo in cui il valore

logico dell’uscita Y è (n.v.) quando

non vincolato 26

l’ingresso di controllo assume il valore logico 0

A differenza delle altre porte viste finora, le uscite di

più buffer tri-state possono essere collegate tra di loro:

quando l’uscita Y di un buffer tri-state è non vincolata,

il suo valore dipende dalle altre porte a cui è collegata.

© 2016

Architettura degli Elaboratori

Collegam. wired OR di buffer tri-state 15

Limitazione: le uscite delle porte tri-state possono

essere collegate tra loro purché di esse sia

al più una 26

vincolata ad un valore logico (0 oppure 1).

E’ possibile realizzare l’OR delle uscite senza l’effettiva

presenza di una porta OR (“wired OR”). In ogni istante solo una

delle due porte è attiva

Y=A se C=1

Y=B se C=0

Funzione di MULTIPLEXER 2/1

(C decide quale segnale passa)

© 2016

Architettura degli Elaboratori

Multiplexer 2/1 (senza buffer tri-state) 16

26

Y=A se C=1

Y=B se C=0

Senza buffer tri-state è necessaria una porta OR la cui

funzione, nella slide precedente, era ottenuta con il

collegamento in parallelo delle due uscite. © 2016

Architettura degli Elaboratori

Porta NAND open collector (1 di 2) 17

Un altro dispositivo che consente collegamenti in

wired OR è la porta open collector.

NAND 26

In tale porta l’uscita è vincolata (al valore logico 0)

solo quando ad entrambi gli ingressi è presente il

valore logico 1. © 2016

Architettura degli Elaboratori

Porta NAND open collector (2 di 2) 18

L’uscita di una porta NAND open collector può

assumere solo il valore logico 0: è dunque possibile 26

attivare contemporaneamente più uscite di porte di

questo tipo visto che i valori ad esse presenti non

possono mai essere contrastanti.

Resistenza di pull-up

Lo schema qui sopra può essere usato per segnalare il

verificarsi di almeno uno tra n possibili eventi. © 2016

Architettura degli Elaboratori

Registro da un bit 19

Un è un dispositivo in grado di

registro memorizzare

(cioè conservare nel tempo) un valore logico. 26

Tale capacità distingue i registri dalle porte logiche.

è il segnale di controllo

w

• il valore di X viene trasferito (memorizzato)

w=1:

nel registro; Y=X

Y rimane al valore memorizzato,

• w=0:

senza risentire di eventuali variazioni di X © 2016

Architettura degli Elaboratori

Registro da un bit: diagramma temporale 20

26

X

Y

w t

w basso: Y rimane “bloccato” © 2016

Architettura degli Elaboratori

Bus 21

Un è un collegamento elettrico tra parti diverse

bus

di un elaboratore che consente il trasferimento di 26

informazione.

Un bus è composto da una o più linee; ogni linea

consente di trasferire un bit.

Per rappresentare un bus di bit si usano i seguenti

n

simboli grafici: © 2016

Architettura degli Elaboratori

Trasferimento di un bit 22

26

=1: il valore presente in R1 viene trasferito sul bus

r 1 =1: il valore sul bus viene memorizzato in R2

w 2

Diagramma temporale dei segnali di controllo:

r 1

w t

2 © 2016

Architettura degli Elaboratori

Trasferimento di gruppi di bit 23

Un po’ di nomenclatura… 26

4 bit: “nibble” (o nybble)

• 8 bit: “byte”

• 16 bit: “half-word”

• 32 bit: “word”

• 64 bit: “double-word”

La definizione di “word” dipende comunque dalla taglia

della parola di memoria della macchina che si sta

considerando (ne parleremo meglio più avanti). © 2016

Architettura degli Elaboratori

Trasferimento in parallelo di più bit 24

26

Vantaggio: velocità

• Svantaggio: servono più linee per il bus

• © 2016

Architettura degli Elaboratori

Shift register 25

Per il trasferimento seriale si utilizza un dispositivo

chiamato (shift

registro a scorrimento register) 26

a ciascun impulso ( ) di S, i bit contenuti nel

• registro scorrono di una posizione verso destra:

- R3 → R4

- R2 → R3

- R1 → R2

- X → R1

Esempio: se inizialmente è e lo shift register contiene

X=1 0111,

dopo un impulso di S lo shift register contiene 1011 © 2016

Architettura degli Elaboratori

Trasferimento seriale di più bit 26

shift register:

Trasferimento seriale tra due 26

C=0: a ciascun impulso ( ) di S, un bit del registro di sx

• viene trasferito al registro di dx e in quest’ultimo viene

X

inserito il valore di

C=1: a ciascun impulso di S, un bit del registro di sx

• viene trasferito al registro di dx

- e viene riportato all’ingresso e inserito nel registro di sx

-

(dopo quattro impulsi di S nel registro di dx risulta

copia

trasferita del contenuto del registro di sx). © 2016

Architettura degli Elaboratori Fine

00.a Reti logiche

Architettura degli Elaboratori © 2016

Testo di riferimento:

[Congiu] - 2.4 (pagg. 37–57)

Reti Logiche Combinatorie

00.b Analisi

Minimizzazione booleana

Sintesi

1

Architettura degli Elaboratori © 2016

Rete logica combinatoria: definizione 2

Una rete logica combinatoria è una rete logica

nella quale, in ogni istante, i valori presenti alle 36

uscite sono determinati unicamente dai valori

presenti agli ingressi nel medesimo istante.

Una rete logica combinatoria è quindi:

priva di stato

• (non contiene elementi di memoria);

interamente descritta dalla sua tabella di verità,

• che definisce, in altrettante colonne, le funzioni

logiche delle variabili di ingresso prodotte alle

uscite. © 2016

Architettura degli Elaboratori

Primo esempio: il decodificatore 3/8 3

Un è una rete

decodificatore

combinatoria che attiva 36

l’i-esima uscita se e solo se

il valore binario codificato

dagli ingressi è i 3

Tabella di verità per un decodificatore con 3 ingressi e 2 =8 uscite:

© 2016

Architettura degli Elaboratori

Decodificatore: realizzazione 4

36

Sono rappresentate

solo le funzioni

F F F

, e .

0 1 4

Le porte NOT

sono rappresentate

con circoletti “ ”.

 © 2016

Architettura degli Elaboratori

Porte logiche: notazione algebrica 5

Simbolo Tabella Notazione

Nome grafico di verità algebrica 36

AND Y = A·B

OR Y = A+B

NOT Y = A

XOR Y = A B

Å © 2016

Architettura degli Elaboratori n

Funzioni logiche di variabili 6

E’ interessante osservare che il numero delle

n variabili è

diverse possibili funzioni logiche di 36

un numero finito.

Ad esempio, le funzioni logiche di due variabili

sono tante quante sono le diverse possibili

tabelle di verità che le definiscono, cioè 16

(quante sono le diverse possibili configurazioni

4

dei quattro valori nell’ultima colonna: 2 =16).

8

=256.

Le funzioni logiche di 3 variabili sono 2 n

2

n variabili sono 2 .

Le funzioni logiche di

Architettura degli Elaboratori © 2016

Reti logiche: rappresentazioni 7

Quanto abbiamo visto per le porte logiche

vale in generale per le reti logiche. 36

equivalenti

In altre parole, sono tra loro

le tre rappresentazioni…

…mediante uno schema grafico

• …mediante una tabella di verità

• …mediante una espressione algebrica

Sceglieremo in ciascun caso la rappresentazione

più opportuna per quel caso. © 2016

Architettura degli Elaboratori

Funzione di equivalenza (1 di 3) 8

E=1 se A=0 e B=0 (A•B=1) 36

E=1 se A=1 e B=1 (A•B=1)

È possibile ottenere E come “somma di prodotti”:

E= A•B+A•B

La funzione che vale 1 quando

è uguale a 1 uno o l’altro dei

suoi due ingressi e l’OR © 2016

Architettura degli Elaboratori

Funzione di equivalenza (2 di 3) 9

E si può ottenere anche come “prodotto di somme”: 36

E=0 se A=0 e B=1 (A+B=0)

E=0 se A=1 e B=0 (A+B=0)

E = (A+B)•(A+B)

La funzione che vale 0 quando

è uguale a 0 uno o l’altro dei

suoi due ingressi e l’AND © 2016

Architettura degli Elaboratori

Funzione di equivalenza (3 di 3) 10

E = A B

Å 36

Diversi circuiti logici equivalenti realizzano

la stessa funzione logica: (E = OR esclusivo negato)

© 2016

Architettura degli Elaboratori

Algebra di Boole o booleana 11

L’analisi delle proprietà delle espressioni 36

algebriche costruite da variabili binarie e

operatori logici, si deve al matematico G. Boole

(1815-1864), ed è nota come algebra booleana.

?

S = B•(A•B) + A•(A•B) © 2016

Architettura degli Elaboratori

Algebra di Boole: proprietà (1 di 2) 12

A 36

A·1 = A A·0 = 0 A·A = A A·A = 0

A = A A+0 = A A+1 = 1 A+A = A

A+A = 1

Proprietà commutativa, associativa e distributiva:

A·B = B·A A+B = B+A A·(B·C) = (A·B)·C

A+(B+C) = (A+B)+C A·(B+C) = A·B+A·C

A+(B·C) = (A+B)·(A+C) © 2016

Architettura degli Elaboratori

Algebra di Boole: proprietà (2 di 2) 13

A 36

Legge di De Morgan:

A + B = A · B oppure A + B = A · B

A · B = A + B A · B = A + B

oppure

ES: © 2016

Architettura degli Elaboratori

Sintesi di un half-adder (1 di 2) 14

36

S’ = A•B+A•B = AÅB

C’ = A•B © 2016

Architettura degli Elaboratori

Sintesi di un half-adder (2 di 2) 15

Utilizziamo l’algebra booleana e le sue proprietà

per riscrivere S’ utilizzando solo porte NAND: 36

S’ = A•B + A•B

S’ = A•B • A•B

S’ = (A•B+B•B) • (A•B+A•A)

S’ = B•(A+B) • A•(A+B)

S’ = B•(A•B) • A•(A•B) © 2016

Architettura degli Elaboratori

Half-adder con sole porte NAND 16

S’ = B•(A•B) • A•(A•B) 36

C’ = A•B © 2016

Architettura degli Elaboratori

Sintesi di un full-adder (1 di 2) 17

36

Half-Adder

S = A•B•C” + A•B•C” + A•B•C” + A•B•C” S’ = (AÅB)

S = (A•B + A•B)•C” + (A•B + A•B)•C”

S = (AÅB)•C” + (AÅB)•C” = (AÅB) C”

Å C’ = A•B

S = S’ C”

Å

C = A•B•C” + A•B•C” + A•B•C” + A•B•C”

C = (A•B + A•B)•C” + A•B•(C” + C”) = (AÅB)•C” + A•B

C = S’•C” + C’ © 2016

Architettura degli Elaboratori

Sintesi di un full-adder (2 di 2) 18

36

S = S’ C”

Å

C = S’•C” + C’ © 2016

Architettura degli Elaboratori

Full-adder con sole porte NAND 19

C = S’•C” + C’ = S’•C” • C’ 36

© 2016

Architettura degli Elaboratori

Sommatore binario da 4 bit 20

36

© 2016

Architettura degli Elaboratori

Sommatore binario da 16 bit 21

36

© 2016

Architettura degli Elaboratori

Minimizzazione: Mappe di Karnaugh (1/7) 22

Tra le proprietà dell’algebra di Boole, le seguenti 36

consentono di semplificare notevolmente le espressioni

booleane:

A•B + A•B = A•(B + B) = A

A•(B•C + B•C + B•C + B•C) = A

Le mappe di Karnaugh sono una particolare forma di

tabella di verità, che consente di individuare

immediatamente la possibilità di fare queste

semplificazioni. Massimizzare il rettangolo © 2016

Architettura degli Elaboratori

Minimizzazione: Mappe di Karnaugh (2/7) 23

Ad esempio, la seguente tabella di verità della funzione Y=Y(A,B,C)

A B C Y A 0 0 1 1 36

B

0 0 0 0 0 1 1 0

può essere ridisegnata così: C

0

0 0 1 1

0 1 0 0 0 0 0

0

1

0 1 1 1 1 1

0 0

1 0 0 1

1

1 0 1 Mappa di Karnaugh della funzione Y

1

1 1 0 1

1 1 1

Nelle mappe di K. i valori della funzione sono scritti dentro le caselle.

Dalla tabella di verità o dalla mappa di Karnaugh è immediato ottenere

come “somma” di “prodotti”, cioè

l’espressione booleana della funzione Y

come OR di tanti termini AND quante sono le caselle in cui la funzione vale 1;

minterm

) è costituito dall’AND delle

ciascuno di questi termini AND (detti

variabili di ingresso, negate oppure no a seconda che il valore della variabile

associato a quella casella sia 0 oppure 1:

Y = A B C + A B C + A B C + A B C

• • • • • • • • © 2016

Architettura degli Elaboratori

Minimizzazione: Mappe di Karnaugh (3/7) 24

Nel caso di funzioni di 4 variabili, ad es. la mappa di

Z=Z(A,B,C,D),

Karnaugh ha 4 righe e quattro colonne: 36

A 0 0 1 1

CD B 0 1 1 0

1

0 0 0

00 1 1 1

0

01 1 1 1 1

11 1 1 1 0

10

Mappa di Karnaugh della funzione Z

I valori delle variabili individuano le “coordinate” delle caselle:

A,B,C,D

le coppie di valori di e (di e associate alle colonne (alle righe)

A B C D)

sono ordinate in modo che tra due caselle adiacenti (della medesima riga

o della medesima colonna) cambi il valore di una sola delle variabili,

mentre quello di tutte le altre rimane lo stesso; ciò vale anche tra le

caselle estreme di ciascuna riga e di ciascuna colonna (che possono

quindi essere considerate “adiacenti”, in senso circolare). © 2016

Architettura degli Elaboratori

Minimizzazione: Mappe di Karnaugh (4/7) 25

In questo modo a ciascuna coppia di caselle adiacenti contrassegnate con il

valore 1 corrispondono, nella espressione booleana, due termini “prodotto” 36

(minterm) nei quali una variabile è presente negata in uno e non negata

nell’altro, mentre tutte le altre variabili hanno lo stesso valore.

E` allora possibile semplificare l’espressione sostituendo quei due termini

con un unico termine nel quale non è più presente la variabile che cambia

valore.

Ad esempio le ultime due caselle della seconda riga nella mappa della

funzione portano alla seguente semplificazione:

Y

A•B•C + A•B•C = A•C © 2016

Architettura degli Elaboratori

Minimizzazione: Mappe di Karnaugh (5/7) 26

Allo stesso modo, quaterne di caselle adiacenti tutte con il valore 1 (sulla

stessa riga o sulla stessa colonna) corrispondono a quattro termini che si

riducono ad uno; ad esempio le quattro caselle della terza riga nella mappa 36

della funzione portano alla seguente semplificazione:

Z

C•D•(A•B + A•B + A•B + A•B) = C•D portano

le quattro caselle della terza colonna nella mappa della funzione Z

alla seguente semplificazione:

A•B•(C•D + C•D + C•D + C•D) = A•B

Così pure quaterne adiacenti disposte secondo un quadrato producono un

unico termine; ad esempio le quattro caselle in basso a sinistra nella mappa

della funzione portano alla seguente semplificazione:

Z

A•C•(B•D + B•D + B•D + B•D) = A•C

Analogo discorso vale per gruppi di otto caselle adiacenti tutte con il

valore 1. © 2016

Architettura degli Elaboratori

Minimizzazione: Mappe di Karnaugh (6/7) 27

Per semplificare l’espressione di una funzione, si individuano, nella mappa di

K., i gruppi di (2 o 4 o 8) caselle adiacenti con il valore 1.

Spesso conviene sfruttare la proprietà che consente di utilizzare

A+A=A, 36

più volte la stessa casella (lo stesso minterm), per formare gruppi diversi e

ottenere il maggior numero di semplificazioni possibile.

Individuando un insieme di gruppi (da 1, 2, 4 o 8) che copra tutte le caselle

in cui compare il valore 1, si ottiene una espressione semplificata,

costituita dall’OR dei termini corrispondenti a ciascun gruppo.

si possono individuare i gruppi segnati in figura:

Ad es. per la funzione Z, 0 0 1 1

A 0 1 1 0

CD B 0 0 1 0

00 1 0 1 1

01 1 1 1 1

11 1 1 1 0

10

A C A B B D

• • •

Si ottiene, immediatamente, l’espressione semplificata Z=A•C+A•B+B•D

: © 2016

Architettura degli Elaboratori

Minimizzazione: Mappe di Karnaugh (7/7) 28

il loro valore è specificato solo

Funzioni booleane parzialmente definite:

per alcune combinazioni dei valori delle variabili.

Le altre combinazioni o non si verificano mai o il valore della funzione non 36

don’t care conditions

interessa: (d.c.c.).

In una mappa di K. è spesso utile inserire un valore 1 al posto di d.c.c. (per

formare ulteriori raggruppamenti).

Es. Funzione parzialmente definita (i trattini individuano d.c.c.):

W

A B C W A 0 0 1 1

0 0 0 - B 0 1 1 0

0 0 1 1 C

0 1 0 - - - - 1

0

0 1 1 -

1 0 0 1 1 - 0 -

1

1 0 1 -

1 1 0 -

1 1 1 0 A 0 0 1 1

Si possono sostituire due B 0 1 1 0

con altrettanti 1:

d.c.c. C 1 - - 1

0 1 - 0 1

1

si forma la quaterna con cui si ottiene l’espressione semplificata: W = B © 2016

Architettura degli Elaboratori

Encoder 29

36

Y

0 X 0 0 1 1

0 X 0 1 1 0

X

X 1

2 3 - 1 - 0

0 0 X 0

1 - - -

0 1 Y 0

X 1

- - - -

1 1 X

0 - - -

1 0 2 Y 1

Analogamente: X 3

Y = X + X = X + X

Y

0 1 3 1 2 3 © 2016

Architettura degli Elaboratori

Multiplexer 30

Invia all’uscita Y il valore dell’ingresso

X selezionato dagli ingressi C

i i 36

X 0

X 1 Y

X 7 0 1 2 3 4 5 6 7

DEC 3/8

2/1

Mux C C C

2 1 0 © 2016

Architettura degli Elaboratori

Demultiplexer 31

X

Invia il valore dell’ingresso all’uscita

Y selezionata dagli ingressi C

i i 36

Y 0

Y 1

Y 2

X Y 3

0 1 2 3

DEC 2/4

C C

1 0 © 2016

Architettura degli Elaboratori

Sintesi a due livelli 32

36

Sintesi come “somma di prodotti”

© 2016

Architettura degli Elaboratori

Sintesi tramite PLA 33

La sintesi a due livelli è alla base della sintesi tramite

PLA = “Programmable Logic Array” 36

All’interno ci sono collegamenti che possono essere

impostati tra gli ingressi (negati e diretti) e le porte

AND e da queste agli OR © 2016

Architettura degli Elaboratori

Sintesi tramite PLA 34

p

Il numero di prodotti (porte AND) che servono è

uguale al numero di righe della tabella di verità in cui 36

una funzione di uscita vale 1

Es: i = 3, o = 3, p = 7

Un’evoluzione di questi dispositivi programmabili sono gli FPGA (Field

Programmable Gate Array), che contengono anche elementi di memoria

e con i quali si possono costruire sistemi combinatori e sequenziali

complessi, quali i microprocessori. © 2016

Architettura degli Elaboratori

Sintesi tramite ROM (1 di 2) 35

Si può sintetizzare una funzione logica scrivendo in una

memoria ROM i valori che la definiscono nella tabella di 36

verità A B C Y

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1 contenuto della

1 1 0 1 cella di

memoria

1 1 1 1 ROM[5] = 1

Indirizzi di memoria

(codificati dagli ingressi X) © 2016

Architettura degli Elaboratori

Sintesi tramite ROM (1 di 2) 36

Nella ROM vi sono

i righe: ogni riga,

2 36

i

individuata dagli

ingressi, contiene MUX

o i

1 bit per ciascuna /1

2

o

delle funzioni di

uscita i

Per una rete con

o

input e output,

serve una ROM di

i

o × 2 bit o

i uscite

ingressi © 2016

Architettura degli Elaboratori Fine

00.b Reti logiche combinatorie

Minimizzazione booleana tramite Mappe di Karnaugh

Tra le proprietà dell’algebra di Boole, le seguenti consentono di semplificare notevolmente le

espressioni booleane:

A B + A B = A (B + B) = A

• • •

A (B C + B C + B C + B C) = A

• • • • •

Le mappe di Karnaugh sono una particolare forma di tabella di verità, che consente di individuare

immediatamente la possibilità di fare queste semplificazioni.

Ad esempio, la seguente tabella di verità della funzione Y = Y(A,B,C)

A B C Y A 0 0 1 1

B

0 0 0 0 0 1 1 0

può essere ridisegnata così: C

0 0 1 0

0 1 0 0 0 0 1 0

0

0 1 1 1

1 0 0 0 0 1 1 1

1

1 0 1 1 Mappa di Karnaugh della funzione Y

1 1 0 1

1 1 1 1

Dalla tabella di verità o dalla mappa di Karnaugh è immediato ottenere l’espressione booleana della

funzione come “somma” di “prodotti”, cioè come OR di tanti termini AND quante sono le caselle in

Y

cui la funzione vale 1; ciascuno di questi termini AND (detti minterm) è costituito dall’AND delle

variabili di ingresso, negate oppure no a seconda che il valore della variabile associato a quella

casella sia 0 oppure 1.

Y = A B C + A B C + A B C + A B C

• • • • • • • •

Nel caso di funzioni di 4 variabili, ad es. la mappa di Karnaugh ha 4 righe e

Z = Z(A,B,C,D),

quattro colonne: A 0 0 1 1

CD B 0 1 1 0

0 0 1 0

00 1 0 1 1

01 1 1 1 1

11 1 1 1 0

10

Mappa di Karnaugh della funzione Z

Nelle mappe di Karnaugh i valori della funzione sono scritti dentro le caselle.

Y

I valori delle variabili sono indicati come “coordinate” delle caselle. Esaminando queste

A,B,C,D

“coordinate, si constata che le coppie di valori di e (di e associate alle colonne (alle righe)

A B C D)

sono ordinate in modo che tra due caselle adiacenti (della medesima riga o della medesima colonna)

cambia il valore di una sola delle variabili, mentre quello di tutte le altre rimane lo stesso; questa

proprietà vale anche tra le caselle estreme di ciascuna riga e di ciascuna colonna (che, sotto questo

aspetto, possono quindi essere considerate “adiacenti”, in senso circolare). 1

Si osserva che, in virtù di questo fatto, a ciascuna coppia di caselle adiacenti contrassegnate con il

valore 1 corrispondono, nella espressione booleana, due termini “prodotto” (minterm) nei quali una

variabile è presente negata in uno e non negata nell’altro, mentre tutte le altre variabili hanno lo

stesso valore. E` allora possibile semplificare l’espressione sostituendo quei due termini con un unico

termine nel quale non è più presente la variabile che cambia valore. Ad esempio le ultime due caselle

della seconda riga nella mappa della funzione portano alla seguente semplificazione:

Y

A B C + A B C = A C

• • • • •

Allo stesso modo, quaterne di caselle adiacenti tutte con il valore 1 (sulla stessa riga o sulla stessa

colonna) corrispondono a quattro termini che si riducono ad uno; ad esempio le quattro caselle della

terza riga nella mappa della funzione portano alla seguente semplificazione:

Z

C D (A B + A B + A B + A B) = C D

• • • • • • •

le quattro caselle della terza colonna nella mappa della funzione portano alla seguente

Z

semplificazione:

A B (C D + C D + C D + C D) = A B

• • • • • • •

Così pure quaterne adiacenti disposte secondo un quadrato producono un unico termine; ad

esempio le quattro caselle in basso a sinistra nella mappa della funzione portano alla seguente

Z

semplificazione:

A C (B D + B D + B D + B D) = A C

• • • • • • •

Analogo discorso vale per gruppi di otto caselle adiacenti tutte con il valore 1.

Per semplificare l’espressione booleana di una funzione, si tratta dunque di individuare, nella relativa

mappa di Karnaugh, i gruppi di (2 o 4 o 8) caselle adiacenti con il valore 1.

Nel far ciò conviene tenere presente la proprietà che consente di utilizzare più volte la

A+A=A,

stessa casella (ovvero più volte lo stesso minterm nell’espressione booleana), per formare gruppi

diversi, al fine di operare il maggior numero di semplificazioni possibile.

Individuando un insieme di gruppi (da 1, 2, 4 o 8) che copre tutte le caselle in cui compare il valore 1,

si ottiene una espressione semplificata, costituita dall’OR dei termini corrispondenti a ciascun gruppo.

Riprendendo l’esempio della funzione si possono individuare i gruppi segnati in figura:

Z, A 0 0 1 1

CD B 0 1 1 0

0 0 1 0

00 1 0 1 1

01 1 1 1 1

11 1 1 1 0

10

A C A B B D

• • •

Con questi raggruppamenti si ottiene, immediatamente, l’espressione semplificata di Z:

Z = A C + A B + B D

• • •

Nell’esempio si può osservare che si sono considerate adiacenti anche le caselle estreme delle righe

o delle colonne.

Si osserva che si possono individuare diversi raggruppamenti che coprono tutte le caselle in cui Z

vale 1, ciascuno dei quali porta a diverse espressioni di equivalenti (più o meno semplificate).

Z 2

Funzioni booleane parzialmente definite

Una funzione booleana si dice parzialmente definita se il suo valore è specificato solo per alcune

combinazioni dei valori delle variabili.

Nella pratica si ha a che fare con funzioni booleane parzialmente definite in due casi: o quando le

altre combinazioni dei valori delle variabili non si possono verificare mai, oppure quando, anche se si

verificano, i corrispondenti valori della funzione non importano (possono essere indifferentemente 0

od 1, perché comunque non vengono usati).

Nella tabella di verità (o nella mappa di Karnaugh) di una funzione parzialmente definita, i valori non

specificati sono comunemente indicati con un trattino e corrispondono a ciò che si chiama

“condizioni di indifferenza”, ovvero don’t care conditions (d.c.c.).

La presenza delle d.c.c. nelle caselle di una mappa di Karnaugh può essere convenientemente

sfruttata, sostituendone alcune con il valore 1, al fine di ottenere gruppi (da 2, 4, 8) che portano a

semplificare l’espressione della funzione.

Ad esempio, considerando la funzione parzialmente definita la cui tabella di verità è riportata qui

W

sotto insieme con la relativa mappa di Karnaugh:

A B C W A 0 0 1 1

B

0 0 0 - 0 1 1 0

C

0 0 1 1

0 1 0 - - - - 1

0

0 1 1 -

1 0 0 1 1 - 0 -

1

1 0 1 -

1 1 0 -

1 1 1 0 A 0 0 1 1

B

Si possono sostituire due 0 1 1 0

C

con altrettanti 1:

d.c.c. 1 - - 1

0 1 - 0 1

1

e individuare la quaterna che consente di ottenere la seguente espressione semplificata di W:

W = B 3

Sintesi di un encoder

Si ricorda che il funzionamento di un encoder è basato sull’ipotesi che, in ogni istante, una e una sola

delle variabili di ingresso abbia il valore 1.

Si consideri il caso dell’encoder con 4 ingressi e due uscite:

X

0 ENC

X Y

1 0

4/2

X Y

2 1

X

3

Le due funzioni d’uscita Y ed Y sono, dunque, parzialmente definite perché le combinazioni di valori

0 1

delle variabili d’ingresso diverse da quelle in cui vi è un solo valore uguale ad 1 non si possono

presentare mai (la rete logica a monte sarà tale da produrre valori di X che soddisfano questa

i

ipotesi).

Delle 16 righe della tabella di verità sono significative solo le 4 nelle quali Y ed Y sono definite:

0 1

X X X X Y Y

0 1 2 3 1 0

1 0 0 0 0 0

0 1 0 0 0 1

0 0 1 0 1 0

0 0 0 1 1 1

. . . . - -

La corrispondente mappa di Karnaugh per la funzione Y è:

0

X 0 0 1 1

0

X 0 1 1 0

X X 1

2 3

0 0 - 1 - 0

0 1 1 - - -

1 1 - - - -

1 0 0 - - -

Sfruttando le condizioni di indifferenza (d.c.c.) presenti in questa mappa, si possono disegnare i due

raggruppamenti da 8 caselle indicati in figura:

X 0 0 1 1

0

X 0 1 1 0

X X 1

2 3

0 0 - 0

1 -

0 1 - - -

1

1 1 - - -

-

1 0 0 - -

-

E ottenere l’espressione semplificata: Y = X + X

0 1 3

Analogamente si può ottenere: Y = X + X

1 2 3 4

Testo di riferimento:

[Congiu] - 2.5 (pagg. 57–76)

Reti Logiche Sequenziali

00.d Latch e flip-flop

Sintesi

Reti sincrone

1

Architettura degli Elaboratori © 2016

Rete logica sequenziale: definizione 2

Una è una rete logica

rete logica sequenziale 33

nella quale i valori presenti alle uscite sono e

determinati dai valori presenti agli ingressi

dal in cui si trova il sistema.

valore dello stato

Una rete logica sequenziale:

contiene elementi di memoria

• è descritta da una tabella di verità in cui si

• tiene conto anche dello stato del sistema © 2016

Architettura degli Elaboratori

Elementi di memoria: esaminiamone alcuni 3

Latch: sensibili al livello dei segnali d’ingresso 33

Latch di tipo R-S

• Latch di tipo R-S con clock

• Latch di tipo D

• Latch di tipo J-K

Flip-flop: sensibili ai fronti dei segnali d’ingresso

Flip-flop di tipo T (2 versioni)

• Flip-flop di tipo D

• Flip-flop di tipo J-K

• © 2016

Architettura degli Elaboratori

Elementi di memoria: latch di tipo R-S 4

33

R = 1 Reset: Q = 0

è

S = 1 Set: Q = 1

è

Q R S Q’

0 0 0 0 S=1

0 0 1 1 R=1 S=1

0 1 0 0

0 1 1 - Q=0 Q=1

1 0 0 1

1 0 1 1 R=1

1 1 0 0 don’t care

1 1 1 - diagramma di stato © 2016

Architettura degli Elaboratori

Latch di tipo R-S con clock 5

33

Gli ingressi R e S esercitano il loro effetto solo

quando il clock C ha valore logico 1 © 2016

Architettura degli Elaboratori

Latch di tipo D 6

Latch tipo R-S 33

Nel latch R-S la configurazione R=S=1 non è valida.

Il latch D risolve questo problema. © 2016

Architettura degli Elaboratori

Latch di tipo D con ingressi asincroni 7

33

NOR Modalità asincrona (C = 0) : si comporta

0 0 0 1 come un Latch R-S

0 0 1 0 Modalità sincrono (R=S=0) : si comporta

0 1 0 0 come un Latch D

0 1 1 0

1 0 0 0 Nota: una porta NOR a 3 ingressi

1 0 1 0 con il terzo ingresso nullo si comporta

1 1 0 0 come una porta NOR a 2 ingressi

1 1 1 0 © 2016

Architettura degli Elaboratori

Latch di tipo J-K 8

Quando Q=1 può esercitarsi solo l’azione

(di reset) di K (posto che sia anche C=1). 33

Quando Q=0 (Q=1) (posto che sia C=1)

può esercitarsi solo l’azione (di set) di J.

AB + A(neg) C = Y

Q K J Q’

0 0 0 0

C=1 0 0 1 1 C=1

0 1 0 0 J=1

0 1 1 1

1 0 0 1 Q=0 Q=1

1 0 1 1

1 1 0 0 K=1

1 1 0

1 diagramma di stato

tabella delle transizioni © 2016

Architettura degli Elaboratori

Latch di tipo J-K 9

Se J=K=C=1: funzione di toggle

L’uscita Q è instabile: si inverte 33

ripetutamente.

La durata del clock C=1 può

essere calibrata per ottenere

una sola commutazione di Q.

Q K J Q’

0 0 0 0

C=1 0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 1

1 0 1 1

1 1 0 0

1 1 1 0

tabella delle transizioni © 2016

Architettura degli Elaboratori

Flip-flop di tipo T (1 di 2) 10

Latch : sensibile al livello 0/1

Flip-flop : sensibile ai fronti

di salita/discesa 33

f T,

ad ogni fronte di salita di

f genera un impulso la cui durata

consente una sola commutazione di Q

© 2016

Architettura degli Elaboratori

Flip-flop di tipo T (2 di 2) 11

33

T 1

®

Q T Q’ T 0 T 0

® ®

0 0 0

® Q=0 Q=1

1 1

0 ® 0 1

1 ® 1 0

1 ® 1

T

®

diagramma di stato © 2016

Architettura degli Elaboratori

Flip-flop di tipo D (Master-Slave) 12

Ingresso e uscita: disaccoppiati 33

Il flip-flop slave memorizza il valore

in ingresso sul fronte di discesa,

con un ritardo di mezzo ciclo di clock

diagramma temporale di un’azione di set © 2016

Architettura degli Elaboratori

Shift register con flip-flop Master-Slave 13

La proprietà di disaccoppiare gli ingressi dalle uscite, 33

consentita dai flip-flop di tipo Master-Slave, risulta

utile nella costruzione di registri a scorrimento. © 2016

Architettura degli Elaboratori

Flip-flop di tipo J-K 14

33

Un’altra configurazione di flip-flop di tipo Master-Slave

è quella del flip-flop J-K.

Il funzionamento si distingue dal latch J-K per:

- la commutazione sui fronti di discesa anziché sul livello

- il disaccoppiamento uscita/ingresso tipico

della configurazione Master-Slave © 2016

Architettura degli Elaboratori

Flip-flop di tipo J-K 15

33

K=1 causa un SET del

latch master (Q’ =1) sul

fronte di salita del clock e

un conseguente reset del

latch slave (Q=0) sul

fronte di discesa del clock © 2016

Architettura degli Elaboratori

Flip-flop T sensibile ai fronti 16

Se eliminiamo gli ingressi J e K da un flip-flop J-K si

ottiene un flip-flop T sensibile ai fronti di discesa. 33

L’uscita oscilla tra 0 ed 1 commutando in corrispondenza

dei fronti di discesa.

Q T Q’ T 0

®

0 0 1

® T 1 T 1

® ®

1 0

0 ® 0 0

1 Q=0 Q=1

® 1 1

1 ® 0

T

®

diagramma di stato

tabella delle transizioni © 2016

Architettura degli Elaboratori

Esempio: contatore binario 17

33

U

3

U

2

U

1

U

0

C t

t

x

All’istante t si ha: U U U U = 0 1 1 1 = 7

x 3 2 1 0 2

Architettura degli Elaboratori © 2016

Sintesi delle reti sequenziali (1 di 2) 18

33

Lo è contenuto in elementi di memoria:

stato del sistema é ù

per Z stati servono P= log Z bit di memoria.

2

Ad ogni istante, una fornisce le uscite

rete combinatoria

e il nuovo valore dello stato in funzione degli ingressi. © 2016

Architettura degli Elaboratori

Sintesi delle reti sequenziali (2 di 2) 19

Una “oculata” riduce la

scelta delle variabili di stato 33

complessità della parte combinatoria, ma non ci sono

regole generali da seguire.

Per la si applicano

sintesi della rete combinatoria

le tecniche già illustrate in precedenza.

Spesso la rete viene realizzata in due parti separate,

secondo uno dei due modelli seguenti:

(1955);

• modello della macchina di Mealy (1956).

• modello della macchina di Moore

I due modelli sono funzionalmente equivalenti. © 2016

Architettura degli Elaboratori

Sintesi: macchina di Mealy 20

33

Rete combinatoria C1: fornisce le uscite in funzione degli ingressi

• e dello stato. C2: fornisce il nuovo stato in funzione degli

Rete combinatoria

• ingressi e del vecchio stato (= stato all’istante precedente). © 2016

Architettura degli Elaboratori

Sintesi: macchina di Moore 21

33

Rete combinatoria C2’: fornisce le uscite in funzione del solo stato.

• Rete combinatoria C1’: fornisce il nuovo stato in funzione degli

• ingressi e del vecchio stato. © 2016

Architettura degli Elaboratori

Parte combinatoria: sintesi con ROM 22

33

N+P

(M+P)•2 bit di ROM;

1.Rete generica:

N+P N+P N+P

M•2 + P•2 = (M+P)•2 bit (come sopra);

2.Mealy: N+P Pbit (sembra minore, ma il numero

+ M•2

P•2

3.Moore: di stati P è in genere maggiore).

Pmo >> Pme © 2016

Architettura degli Elaboratori

Esempio di sintesi: interruttore 23

i l l

Un interruttore , due lampadine e .

1 2

Assegnazione degli stati logici all’interruttore e alle lampadine: 33

0 = interruttore aperto, 1 = interruttore chiuso (premuto);

• 0 = lampadina spenta, 1 = lampadina accesa.

Specifica di funzionamento

Interruttore aperto (X=0):

• =Y =0).

le lampadine sono entrambe spente (Y 1 2

Interruttore chiuso (X=1):

• si accende a turno una delle due lampadine. © 2016

Architettura degli Elaboratori

Esempio di sintesi: diagramma di stato 24

4 stati 33

2 bit di stato

Specifica di funzionamento

Interruttore aperto (X=0):

• le lampadine sono entrambe spente (Y =Y =0).

1 2

Interruttore chiuso (X=1):

• si accende a turno una delle due lampadine. © 2016

Architettura degli Elaboratori

Esempio di sintesi: modello 25

33

© 2016

Architettura degli Elaboratori

Esempio di sintesi: parte combinatoria 26

33

© 2016

Architettura degli Elaboratori

Esempio di sintesi: versione 1 27

Y = S ·X S’ = Y + (S )·X

ÅS

1 1 1 2 1 2

= S ·X = X

Y S’ 33

2 1 2

Latch R-S come elementi di memoria: rete sequenziale asincrona

© 2016

Architettura degli Elaboratori

Esempio di sintesi: “revisione” 28

S2 = X: si può fare a meno di S2?

Sì, ma i passaggi di stato devono avvenire sulle variazioni di X 33

l

S=0: la prossima lampadina ad accendersi sarà

• 1

l

S=1: la prossima lampadina ad accendersi sarà

• 2

Lo stesso valore (X=1) che porta da S=0 a S=1, porta anche

da S=1 a S=0: le transizioni vanno sincronizzate da un clock.

E’ necessaria una rete sequenziale .

sincrona

• © 2016

Architettura degli Elaboratori

Esempio di sintesi: versione 2 29

33

Serve un flip-flop, ad es. di tipo J-K master-slave.

Le funzioni di clock, che sincronizza le transizioni, qui sono svolte da X.

© 2016

Architettura degli Elaboratori

Esempio di sintesi: versione 3 30

In modo più sbrigativo, senza seguire il procedimento di sintesi e di

minimizzazione delle funzioni booleane, l’esame della tabella di verità

e l’esperienza del progettista portano a riconoscere che S’ = SÅX 33

descrive un e consentono sintesi più semplice.

flip-flop di tipo T © 2016

Architettura degli Elaboratori

Sincronizzazione di più reti 31

Nelle reti logiche reali i tempi di propagazione sono

non nulli: questo può essere uno svantaggio, ma 33

consente anche di operare simultaneamente i diversi

passi di una catena di elaborazioni:

Le uscite all’istante t delle reti combinatorie C fungono

i

da ingressi per la rete C all’istante t (pipeline).

i+1 i+1

Un clock sincronizza le elaborazioni, assicurando che gli

acquisiscano valori corretti.

elementi di memoria S

i © 2016

Architettura degli Elaboratori

Limiti sul periodo del clock 32

Diagramma temporale del sistema precedente: 33

t : periodo del clock

cy

t : tempo “di sicurezza”

s

t : tempo di memorizzaz.

d

t : tempo di propagazione

p x’

x x x’

1

1 2 2

S C S C

1 1 2 2

Deve essere:

t t + t + t

³ s d p

cy © 2016

Architettura degli Elaboratori

Ingressi e uscite nei medesimi registri 33

33

Ingressi e uscite della rete combinatoria C possono

essere memorizzati nei medesimi registri S. © 2016

Architettura degli Elaboratori Fine

00.d Reti logiche sequenziali

Schema Nome Funzioni Particolarità

LATCH RESET- R = 1 : Reset : Q = 0 Se S=1 e R=1,

SET R = 0 : Set : Q = 1 l’azione di SET non

(LATCH R-S) funziona; inoltre non

è più vero che P è

P = Q negato uguale a Q negato

LATCH R-S con Se C = 1 (clock alto) Le funzioni di SET e

CLOCK R = 1 : Reset : Q = 0 RESET sono limitate

R = 0 : Set : Q = 1 nel tempo: possono

essere azionate solo

Aggiunge due porte quando il clock è alto

AND che abilitano

R e S solo in

presenza di clock

alto

LATCH D Solo se C = 1 La configurazione

D = 0 : Reset : Q = 0 R=S=1 non è più

D = 1 : Set : Q = 1 impostabile

Evita la

configurazione R =

1 e S = 1 Di fatto, se C = 1, Q

memorizza il valore di D

LATCH D con Se C = 0 Può funzionare sia

ingressi RS R = 1 : Reset : Q = 0 come un normale

R = 0 : Set : Q = 1 LATCH D (modalità

sincrona), sia come

Rete ibrida tra un un LATCH R-S

latch D e un latch Se R = 0 e S = 0 (modalità asincrona)

R-S Se C = 1

D = 0 : Reset : Q = 0

D = 1 : Set : Q = 1

LATCH J-K Se C = 1 Le funzioni di SET e

K = 1 : Reset : Q = 0 RESET sono abilitate

J = 1 : Set : Q = 1 solo quando il clock è

Aggiunge due linee alto; inoltre le linee di

di feed-back feedback fanno in

Reset avviene solo se modo che una volta

Q=1 impostato Q =1, sia

Set avviene solo se Q=0 solo possibile fare

RESET, mentre se

Q=0 sia solo

possibile fare SET.

Fintanto che J=1 e

K=1 e C=1, Q

continua a invertirsi

continuamente

FLIP FLOP T Ad ogni periodo di clock, Il circuito formatore

il valore di Q si inverte. genera una

condizione

Aggiunge un equivalente a

circuito formatore al J=K=C=1 della

latch J-K durata giusta per fare

invertire una sola

Il circuito rende la volta il valore di Q

rete sensibile non

più al valore alto

del clock ma al

fronte di salita

FLIP FLOP D Se C = 1 Il valore di Q cambia

(Master-Slave) D = 0 : Reset : Q = 0 valore mezzo clock

D = 1 : Set : Q = 1 dopo il cambio di

valore di D

Due Latch D in

configurazione

Master-Slave, il

master attivo a

clock alto, lo slave

a clock basso

FLIP FLOP JK Se C = 1 Il valore di Q cambia

K = 1 : Reset : Q = 0 valore mezzo clock

J = 1 : Set : Q = 1 dopo il cambio di

Un latch JK e un valore di D

latch RS con clock

in configurazione Reset avviene solo se

Master-Slave, il Q=1

master (JK) attivo a Set avviene solo se Q=0

clock alto, lo slave

(RS) a clock basso

Simboli: LATCH D FLIP FLOP T FLIP FLOP T

con controllo anche

LATCH R-S LATCH D LATCH J-K (fronte di salita) (fronte di discesa)

asincrono u00_za_RetiLogiche.doc

ESERCIZI

ARCHITETTURA DEGLI ELABORATORI 1

0.2 – Prerequisiti: RETI LOGICHE

0.2.1 RETI COMBINATORIE

1. Si scriva la tabella di verità della funzione Y realizzata dalla rete combinatoria di figura 2.11 (T2, pg. 32) e la si

confronti con quella della figura 2.8 (T2, pg. 31)

[Nota: qui e in seguito con la notazione Tx, ci si riferisce al cap. x del libro ‘Architettura degli Elaboratori” di S.

Congiu, ed. Patron, 2007]

2. Si scriva la tabella di verità della funzione Y realizzata dalla rete combinatoria di figura 2.13 (T2, pg. 33),

, A , B , B , e verificare che lo schema realizza, in logica negativa, un

limitandosi a considerare solo i 4 ingressi A

1 2 1 2

wired OR. l l ed

3. Si consideri il serbatoio disegnato in figura, contenente un liquido il cui livello deve rimanere compreso tra 1

l t t t

e la cui temperatura deve rimanere compresa tra ed .

2 1 2

Vi sono appositi sensori che generano i seguenti segnali booleani:

= 1 se l > l x = 1 se l < l x = 1 se t > t x = 1 se t < t

x 1 1 2 2 3 1 4 2

x = 0 se l l x = 0 se l l x = 0 se t t x = 0 se t t

£ ³ £ ³

1 1 2 2 3 1 4 2

Per mantenere le condizioni desiderate si agisce su 3 valvole controllate dai seguenti segnali booleani:

= 1:

y valvola di immissione liquido freddo aperta

1

y = 0: valvola di immissione liquido freddo chiusa

1 = 1:

y valvola di immissione liquido caldo aperta

2

y = 0: valvola di immissione liquido caldo chiusa

2 = 1:

y valvola di scarico del liquido aperta

3

y = 0: valvola di scarico del liquido chiusa

3 y aperto: y = 1

y

2 1

1

caldo freddo

x = l < l l

2 2 2

l

x = l > l l

1 1 1 x = t < t

t 4 2

2

t x = t > t

t 3 1

1

y

3 scarico

Si sintetizzi la rete combinatoria che realizza il sistema di controllo del livello e della temperatura. y y y

La rete combinatoria richiesta avrà 4 ingressi e 3 uscite: si tratta di sintetizzare le 3 funzioni booleane , ,

1 2 3

x x x x

delle 4 variabili booleane , , , :

1 2 3 4

x

1 y

1

x

2 y

2

x

3 y

3

x

4 u00_za_RetiLogiche.doc

0.2.2 RETI SEQUENZIALI

4. Sintetizzare una rete sequenziale che realizzi un semaforo controllato a mano, secondo lo schema di figura.

V

X G

R

X

1

X è un segnale logico generato dall’interruttore (a molla): t

0 chiuso aperto

Ogni volta che si agisce con l’interruttore (pigiandolo e rilasciandolo ), si vuole che si

accendano,in sequenza,le lampade V, G, R, G, V, G, R, G, … u00_zb_RetiLogicheSol.doc

SOLUZIONI DEGLI ESERCIZI

ARCHITETTURA DEGLI ELABORATORI 1

0.2 – Prerequisiti: RETI LOGICHE

0.2.1 RETI COMBINATORIE

1. Si scriva la tabella di verità della funzione Y realizzata dalla rete combinatoria di figura 2.11 (T2, pg. 32) e la si

confronti con quella della figura 2.8 (T2, pg. 31)

C A B Y

0 1 0 0

0 1 1 1

0 0 0 0

0 0 1 1

1 1 0 1

1 1 1 1

1 0 0 0

1 0 1 0

2. Si scriva la tabella di verità della funzione Y realizzata dalla rete combinatoria di figura 2.13 (T2, pg. 33),

, A , B , B , e verificare che lo schema realizza, in logica negativa, un

limitandosi a considerare solo i 4 ingressi A

1 2 1 2

wired OR.

A B A B Y

1 1 2 2

0 0 1 0 1

0 0

0 1 1

0 0 0 0 1

0 1

0 0 1 1

0 1 1 0 0

0 1 1 1 1

0 1 0 0 1

0 1 0 1 1

1 0 1 0

0 1 1 0

1

1 0 0 0 1

1 0 0 1 1

1 1 1 0 0

1 1 1 1 0

1 0

1 0 0

1 0 1

1 0 Y = A •B • A •B

1 1 2 2

Y = A •B + A •B (De Morgan)

1 1 2 2 u00_zb_RetiLogicheSol.doc

l l ed

3. Si consideri il serbatoio disegnato in figura, contenente un liquido il cui livello deve rimanere compreso tra 1

t t t

l e la cui temperatura deve rimanere compresa tra ed .

2 1 2

Vi sono appositi sensori che generano i seguenti segnali booleani:

x = 1 se l > l x = 1 se l < l x = 1 se t > t x = 1 se t < t

1 1 2 2 3 1 4 2

x = 0 se l l x = 0 se l l x = 0 se t t x = 0 se t t

£ ³ £ ³

1 1 2 2 3 1 4 2

Per mantenere le condizioni desiderate si agisce su 3 valvole controllate dai seguenti segnali booleani:

= 1:

y valvola di immissione liquido freddo aperta

1

y = 0: valvola di immissione liquido freddo chiusa

1 = 1:

y valvola di immissione liquido caldo aperta

2

y = 0: valvola di immissione liquido caldo chiusa

2 = 1:

y valvola di scarico del liquido aperta

3

y = 0: valvola di scarico del liquido chiusa

3 y aperto: y = 1

y

2 1

1

caldo freddo

x = l < l l

2 2 2

l

= l > l

x l

1 1 1 x = t < t

t 4 2

2

t x = t > t

t 3 1

1

y

3 scarico

Si sintetizzi la rete combinatoria che realizza il sistema di controllo del livello e della temperatura. y y

y , ,

La rete combinatoria richiesta avrà 4 ingressi e 3 uscite: si tratta di sintetizzare le 3 funzioni booleane 1 2 3

x x x x

delle 4 variabili booleane , , , :

1 2 3 4

x

1 y

1

x

2 y

2

x

3 y

3

x

4 u00_zb_RetiLogicheSol.doc

SOLUZIONE DELL’ESERCIZIO 3 SULLE RETI COMBINATORIE:

x = 0, x = 0

Si può constatare che la combinazione non può mai verificarsi;

1 2

x = 0, x = 0.

né può mai verificarsi la combinazione 3 4

y y x x x x

y , , , funzioni delle 4 variabili logiche , , , , alle combinazioni

Nella tabella di verità delle funzioni logiche 1 2 3 1 2 3 4

che non possono mai verificarsi corrispondono condizioni di indifferenza (don’t care conditions).

La tabella di verità può, pertanto, essere scritta, in forma semplificata (senza scrivere tutte le righe corrispondenti alle

condizioni di indifferenza):

x x x x y y y

1 2 3 4 1 2 3

0 0 * * – – –

* * 0 0 – – – ß se il livello e la temperatura sono troppo bassi, aggiungere liquido caldo.

0 1 0 1 0 1 0 ß (con y y y

ragionamenti analoghi si scrivono i valori di 1 2 3

1 1 0 0 0

0 1 necessari per reagire nel modo indicato dalle specifiche alle diverse situazioni

0 1

1 1 1 1 0 rilevate dai sensori)

0 0 1 1 1

1 0

1 1

0 1 0 0 1

1 0

0 1 1 0 1

1 0

1 0 1 1 0

1 1 0 0 0

1 1

1 0

1 1 1 0 0 y y y

Si possono ora disegnare le mappe di Karnaugh per le 3 funzioni :

1 2 3

x x

1 2

y 0 0 0 1 1 1 1 0

1 – – – – ß x

0 0 4

0 1 0 0 0

x x

3 4 – ß x x

1 1 1 0 0 •

1 3

1 0 1 1 1 •

y = x + x x

1 4 1 3

x x

1 2

y 0 0 0 1 1 1 1 0

2 – – – – ß x

0 0 3

0 1 1 1 1

x x

3 4 – ß x x

1 1 1 0 0 •

1 4

1 0 0 0 0 •

y = x + x x

2 3 1 4

x x

1 2

y 0 0 0 1 1 1 1 0

3 – – – – ß x

0 0 2

0 1 0 0 1

x x

3 4 –

1 1 0 0 1

1 0 0 0 1 y = x

3 2

Sulla base delle 3 espressioni ottenute, è ora possibile disegnare la corrispondente rete combinatoria che realizza le 3

y y x x x x

y , , delle 4 variabili booleane , , , .

funzioni booleane 1 2 3 1 2 3 4 u00_zb_RetiLogicheSol.doc

0.2.2 RETI SEQUENZIALI

4. Sintetizzare una rete sequenziale che realizzi un semaforo controllato a mano, secondo lo schema di figura.

V

X G

R

X

1

X è un segnale logico generato dall’interruttore (a molla): t

0 chiuso aperto

Ogni volta che si agisce con l’interruttore (pigiandolo e rilasciandolo ), si vuole che si

accendano,in sequenza,le lampade V, G, R, G, V, G, R, G, … u00_zb_RetiLogicheSol.doc

SOLUZIONE DELL’ESERCIZIO 4 SULLE RETI SEQUENZIALI:

Si constata che la sequenza che si ripete è: V, G, R, G.

Adottando ilmodello della macchina di Moore,in cui i valori delle uscite V, G, R dipendono solodallo stato, con 4 stati

diversi si rappresentano le 4 fasi della sequenza. ed S ; si può fissare ad arbitrio la corrispondenza tra stati ed

4 stati diversi si rappresentano con 2 variabili di stato:S

0 1

uscite: variabili

stato uscite

di stato

S S V G R Dalla tabella di verità si ottiene:

1 0

0 0 0 1 0 0 S S

1 0 1 0 1 0 V = •

1 0

S S + S S S

2 1 0 0 0 1 G = =

• •

1 0 1 0 0

S S

3 1 1 0 1 0 R = •

1 0

S S

0 1

Si può ora disegnare lo schema: X T T V

G

R

Gli stati si susseguono nella sequenza 01230123…, ottenibile con un

contatore modulo 3, che conti gli impulsi di X (costituito da due flip-flop

di tipo T collegati in serie, all’ingressodei quali venga inviato X).

Testo di rif.to:

[Congiu] - 3.1, 3.2 (pg. 80–93)

Struttura di un elaboratore

01.b Blocchi funzionali

La memoria centrale

Suddivisione in blocchi funzionali 1

26

I blocchi funzionali di un elaboratore © 2016

Architettura degli Elaboratori

Organizzazione dei bus 2

26

due bus distinti: uno per la memoria, uno per i dispositivi di input-output

© 2016

Architettura degli Elaboratori

Organizzazione dei bus 3

26

elaboratore con bus unico © 2016

Architettura degli Elaboratori

Caratteristiche della memoria centrale 4

Ogni locazione (tipicamente byte) è individuata da un

indirizzo. 26

Con un indirizzo da sono indirizzabili un totale di

N bit

10 20 30

N (nota: 2 = 1024 = 1K, 2 = 1M, 2 = 1G).

locazioni

2

I n realtà spesso solo una parte di queste corrisponde a memoria

effettivamente presente e quindi indirizzabile.

Per motivi di efficienza, le singole operazioni di lettura e

di scrittura interessano unità più ampie:

16 bit: word (halfword), ...

● 32 bit: longword (word), ...

● 64 bit: quadword (doubleword). ...

● ora sostituiti da:

nomi usati nel testo: in futuro: © 2016

Architettura degli Elaboratori

Classificazione delle memorie 5

Principio di funzionamento:

STATICHE (SRAM) il bit è memorizzato in un latch o flip-flop

● 26

– più veloci (memorie cache), dissipano poca potenza (dispositivi portatili),

– non richiedono refresh, più costose (almeno 4 transistor per bit);

DINAMICHE (DRAM) il bit è la carica di un condensatore (refresh)

● – meno veloci, richiedono refresh, ma meno costose (1 transistor per bit).

Funzioni:

RAM (rwm) read-write

● ROM read-only

● PROM programmable ROM

tipi di prom erase time write read esempi d’uso

EPROM 20 m (chip) 100 ms 200 ns bios, monitor, …

E2PROM 5 ms (byte) 5 ms 35 ns cellulari, sintonizzatori,

FLASH 1 s (sector) 100 ms 200 ns foto digitali, mp3, bios, …

© 2016

Architettura degli Elaboratori

Ordinamento dei byte in memoria 6

Big-endian e Little-endian sono i termini che

descrivono l'ordine con cui una elaboratore

immagazzina i byte in una parola da 16 o 32 bit. 26

è l'ordine per cui la parte più significativa

Big-endian

(BIG END) viene memorizzata per prima (all'indirizzo più

basso di memoria).

è l'ordine per cui la parte meno significativa

Little-endian

(LITTLE END) viene memorizzata per prima.

Jonathan Swift, nel libro “I racconta

viaggi di Gulliver”,

che i erano una fazione conservatrice che

Big Endians

rompeva le uova sode dalla parte più larga del guscio, in

contrapposizione al re dei Lillipuziani che richiedeva ai

suoi sudditi (i di aprire le uova dalla punta.

Little Endians)

In realtà, come per le uova, anche nelle memorie, le due

alternative sono entrambe utilizzabili e utilizzate. © 2016

Architettura degli Elaboratori

Ordinamento dei byte: little endian 7

7 0 15 8 7 0 0 26

0 $1D 1 $2C $1D 0

1 $2C 3 $4A $3B 2

2 $3B 5 ‘I ‘C 4

3 $4A 7 ‘O ‘A 6

4 ‘C Word

5 ‘I 31 16 15 0

6 ‘A’ 3 $4A $3B $2C $1D 0

7 ‘O 7 ‘O ‘A ‘I ‘C 4

byte Long-word

Organizzazione little endian: numero $4A3B2C1D E STRINGA “CIAO”

© 2016

Architettura degli Elaboratori

Ordinamento dei byte: big endian 8

7 0 15 8 7 0 0 26

0 $1D 0 $1D $2C 1

1 $2C 2 $3B $4A 3

2 $3B 4 ‘C ‘I 5

3 $4A 6 ‘A ‘O 7

4 ‘C Word

5 ‘I 31 16 15 0

6 ‘A’ 0 $1D $2C $3B $4A 3

7 ‘O 4 ‘C ‘I ‘A ‘O 7

byte Long-word

Organizzazione big endian: numero $1D2C3B4A E STRINGA “CIAO”

© 2016

Architettura degli Elaboratori

Ordinamento dei byte: little o big endian? 9

I computer storici (IBM370), molti RISC e i processori

Motorola usano il metodo big-endian. 26

Dell'altro partito sono, ad esempio, i processori INTEL

che adottano l’ordinamento little-endian, ritenuto più

conveniente nella trasmissione dei dati, ove è trasmessa

per prima la parte meno significativa.

Il PowerPC e l'ARM possono funzionare in tutte e due le

modalità.

Anche nei formati grafici vi sono scelte diverse:

GIF -- Little Endian

● JPEG -- Big Endian

● © 2016

Architettura degli Elaboratori

Accesso alla memoria 10

26

© 2016

Architettura degli Elaboratori

Accesso alla memoria: lettura 11

indirizzi 26

indirizzo memorizzato in MAR

MA

MRD lettura del dato dalla memoria

r dato memorizzato in MBR

W

B dato disponibile sul bus

dati t

© 2016

Architettura degli Elaboratori

Accesso alla memoria: scrittura 12

indirizzi 26

dati indirizzo memorizzato in MAR

MA

MWR dato memorizzato in MBR

W

B scrittura del dato in memoria

w t

© 2016

Architettura degli Elaboratori

Tempo di accesso 13

Tempo di accesso (t ): 26

a

tempo necessario per completare un’operazione

di lettura o scrittura

Il tempo è misurato a partire dall’istante in cui

l’indirizzo fornito dalla CPU è valido (i livelli di

tensione nelle linee indirizzi si sono stabilizzati).

Tale istante corrisponde all’attivazione del

address strobe ’ (AS)

segnale denominato ‘

(il segnale MA nel nostro schema semplificato)

© 2016

Architettura degli Elaboratori

Temporizzazione: READ da SRAM 14

26

(MA) Lettura dei dati

(MRD) I dati saranno pronti

Tempo di accesso t tra un periodo di clock

a Lettura senza stati di attesa © 2016

Architettura degli Elaboratori

READ da SRAM lenta 15

26

(MA) Lettura dei

(MRD) dati

I dati saranno pronti

I dati non saranno pronti tra un periodo di clock

tra un periodo di clock

Lettura con stati di attesa © 2016

Architettura degli Elaboratori

Sincronizzazione degli accessi 16

26

Temporizzazione della CPU per l’istruzione Incremento diretto della memoria

© 2016

Architettura degli Elaboratori

Tempi di accesso 17

Memorie statiche (SRAM):

• 1.4 ÷ 15 ns (high speed) 26

• 35 ÷ 100 ns (low power)

Memorie dinamiche (DRAM):

• 50 ÷ 70 ns (DRAM asincrone)

• 7 ÷ 12 ns (SDRAM sincrone)

(+ latenza: per il primo dato ci vuole un tempo

4-5 volte quello per i dati successivi) © 2016

Architettura degli Elaboratori

Accesso ad un chip SRAM da 128 byte 18

26

128x8

(1Kb) © 2016

Architettura degli Elaboratori

Accesso ad un chip SRAM da 1KB 19

26

© 2016

Architettura degli Elaboratori

Accesso ad una SRAM da 4KB 20

26

© 2016

Architettura degli Elaboratori

Elemento di memoria dinamica: write 21

row select 26

transistor

condensatore bit line

Operazione di scrittura: bit line

1- imposta il valore (H o L) nella (bit da memorizzare);

row select

2- seleziona la riga (attiva ): il transistor diventa un

bit line

interruttore chiuso e la tensione della si trasferisce ai

capi del condensatore (caricandolo o scaricandolo);

row select viene disattivato, il transistor diventa un

quando il

interruttore aperto e il condensatore conserva la carica

(mantiene memorizzato il bit). © 2016

Architettura degli Elaboratori

Elemento di memoria dinamica: read 22

row select 26

transistor

condensatore bit line

Operazione di lettura:

bit line

1- precarica la a circa metà della tensione H;

row select

): il transistor diventa un

2- seleziona la riga (attiva

interruttore chiuso e il verso della corrente che circola tra

bit line

condensatore e la rivela il bit memorizzato (se il

condensatore memorizzava un valore H o L); così però viene

alterata la carica del condensatore;

3- memorizza in un latch il valore (H o L) letto e lo riscrive

(ripristina la carica del condensatore). © 2016

Architettura degli Elaboratori

Elemento di memoria dinamica: refresh 23

rowselect 26

transistor

condensatore bit line

Operazione di refresh:

1- esegue un’operazione di lettura su tutte le celle

della stessa riga (tutti i bit della riga vengono letti,

memorizzati in altrettanti latch e poi riscritti). © 2016

Architettura degli Elaboratori

Accesso ad un chip DRAM da 64Kb 24

26

Chip di memoria dinamica da 64K x 1 bit © 2016

Architettura degli Elaboratori

Refresh 25

DRAM 64Kx1 (256 righe x 256 colonne) 26

Periodo di refresh di ciascun bit = 4 ms

t = 60ns

a

Se si operasse il refresh un bit alla volta:

10 61 ns

= 4 ms / (64·2 )

●t »

r 100%

●l’impegno percentuale sarebbe »

Refresh di un’intera riga alla volta:

16 s

●t = 4 ms / 256 µ

»

r 0.4%

●impegno percentuale=(60 ns/16 µs)*100 » © 2016

Architettura degli Elaboratori

Accesso ad una DRAM da 1MB 26

26

Memoria dinamica da 1MB ottenuta con 16 banchi da 8 chip da 64Kx1

© 2016

Architettura degli Elaboratori

Legge di Moore (transistor/chip) dal 1970 27

Scala 26

logaritmica …x2

ogni 18 mesi

…x1000

ogni 15 anni

© 2016

Architettura degli Elaboratori

Legge di Moore (memorie flash) 28

26

(x1000 in 10 anni!) © 2016

Architettura degli Elaboratori

Legge di Moore per le memorie DRAM? 29

26

© 2016

Architettura degli Elaboratori

Legge di Moore per le prestazioni DRAM? 30

Processor - DRAM Memory Gap 26

µProc: 60%/yr. (2X/1.5yr)

1000000 “Moore’s Law” CPU

Performance 10000 Processor-Memory

Performance Gap:

(grows 50% / year)

100 Less’ Law? DRAM

1

80 82 84 86 88 90 92 94 96 98 00 02 04

19 19 19 19 19 19 19 19 19 19 20 20 20

Year DRAM: 9%/yr. (2X/10 yrs)

© 2016

Architettura degli Elaboratori Fine

01.b Struttura di un elaboratore

Testo di rif.to:

[Congiu] - 3.3-3.6 (pg. 94-112) Il processore PD32

01.e Modulo di controllo

Modulo ALU

Interfacce di I/O

Le istruzioni del PD32

Modulo di controllo 1

1 - FETCH: 24

PC MAR

®

L[MAR] MBR

®

IR

MBR ® PC

PC+4 ®

2 – DECODE

3 - EXECUTE © 2016

Architettura degli Elaboratori

Modulo ALU 2

24

© 2016

Architettura degli Elaboratori

Condition Codes (CC) 3

I più comuni sono i seguenti. 24

• (carry): bit di riporto;

C

• (negative): N=1 indica che il risultato è negativo

N

secondo la convenzione del complemento a 2;

• (zero): Z=1 indica che il risultato è nullo;

Z

• (overflow): V=1 indica che il risultato è affetto da

V

overflow nell’aritmetica con numeri interi (signed);

• (parity): P=1 indica che il risultato contiene un

P

numero pari di bit uguali a 1. © 2016

Architettura degli Elaboratori

Operazioni col Modulo ALU 4

24

Esempi di esecuzione di alcune operazioni © 2016

Architettura degli Elaboratori

Modulo ALU 5

OP1+OP2→RES

S =0, S =0, X =0, OP=0,

1 2 CI

=0, W =1

X CO C 24

OP1-OP2→RES

S =0, S =1, X =1, OP=0,

1 2 CI

X =0, W =1

CO C

-OP1→RES

S =1, S =2, X =1, OP=0,

1 2 CI

OP1-1→RES

=0, S =3, X =0, OP=0,

S 1 2 CI

=0, W =1

X CO C © 2016

Architettura degli Elaboratori

Accesso ai registri dell’ALU 6

R1 + R7 R7

® 24

Invio all’ALU degli operandi (R1) e (R7):

R1 DATA1:

per ottenere ®

REG1=1 (s =1), READ1=1

1

per ottenere R7 DATA2:

®

REG2=7 (d =1), READ2=1

7

(DATA1 DATA2

e operandi inviati all’ALU)

(WRITE DATA risultato ricevuto dall’ALU)

Invio del risultato dall’ALU a R7:

WRITE DATA R7:

per ottenere ®

REG2=7 (d =1), WRITE=1

7 © 2016

Architettura degli Elaboratori

Interfaccia di un dispositivo di input 7

24

PROTOCOLLO:

READY[DISP] = ?

0: aspetta e riesamina

1: START[DISP] = 1

.

.

.

READY[DISP] = ?

0: aspetta e riesamina

1: IORD[DISP] = 1 © 2016

Architettura degli Elaboratori

Protocollo di input 8

segnali DISP

CPU

READY[DISP] = ? 24

0: aspetta e riesamina avvia l’operazione

1: START[DISP] = 1 STARD = 1

. .

STATUS

0 ®

. .

. .

READY[DISP] = ? COMPLETE = 1 DATA BUFFER

Dato ®

0: aspetta e riesamina 1 STATUS

®

DATA BUFFER linee dati

1: IORD[DISP] = 1 ® © 2016

Architettura degli Elaboratori

Interfaccia di un dispositivo di output 9

24

PROTOCOLLO:

READY[DISP] = ?

0: aspetta e riesamina

1: IOWR[DISP] = 1

START[DISP] = 1

READY[DISP] = ?

0: aspetta e riesamina

1: output completato

© 2016

Architettura degli Elaboratori

Struttura del processore PD32 10

24

© 2016

Architettura degli Elaboratori

Realizzazione della fase di FETCH 11

R =1, MA=1

PC MAR

® PC 24

Z=2, MRD=1, W =1

L[MAR] MBR IR

® ® IR

X =1, S =6, S =0, X =0,

PC+4 PC

® 2 1 2 CI

=1, W =1

OP=0, R A PC

Le operazioni indicate a sinistra si ottengono con le

sequenze di segnali di controllo riportate a destra.

In queste sequenze, per semplicità, non sono specificate

le relazioni temporali tra i segnali:

per quanto tempo ciascun segnale conserva il valore,

● quali valori possono essere assunti in parallelo,

● quali valori devono essere assunti in serie.

● © 2016

Architettura degli Elaboratori

Struttura del processore PD32 12

24

PC MAR

®

R =1, MA=1

PC

L[MAR] MBR IR

® ®

Z=2, MRD=1, W =1

IR

PC+4 PC

®

X =1, S =6, S =0, X =0, OP=0,

2 1 2 CI

R =1, W =1

A PC © 2016

Architettura degli Elaboratori

Modulo ALU 13

24

PC MAR

®

R =1, MA=1

PC

L[MAR] MBR IR

® ®

Z=2, MRD=1, W =1

IR

PC+4 PC

®

X =1, S =6, S =0, X =0, OP=0,

2 1 2 CI

=1, W =1

R A PC © 2016

Architettura degli Elaboratori

Codifica di una istruzione nel PD32 14

24

MOVL R0, R1 20002001

Þ © 2016

Architettura degli Elaboratori

Esecuzione delle istruzioni 15

Istruzione di un linguaggio di alto livello:

Z := X + Y 24

(nel linguaggio assembly i nomi delle variabili X, Y, Z

possono essere usati per rappresentare indirizzi di

memoria)

Il PD32 non è in grado di sommare due operandi in

memoria (almeno uno deve essere in un registro dell’ALU).

L’istruzione di assegnazione va quindi espansa nella

sequenza di istruzioni macchina:

MOVL X, R0

ADDL Y, R0

MOVL R0, Z © 2016

Architettura degli Elaboratori

Codifica delle istruzioni nel PD32 16

24

dati Organizzazione dei dati e

delle istruzioni in memoria

istruzioni © 2016

Architettura degli Elaboratori

Esecuzione delle istruzioni nel PD32 - 1 17

24

© 2016

Architettura degli Elaboratori

Struttura del processore PD32 18

MOVL X, R0

fetch: 24

R =1, MA=1,

PC

Z=2, MRD=1, W =1,

IR

=1, S =6, S =0, X =0, OP=0,

X 2 1 2 CI

=1, W =1

R A PC

indirizzo di X:

R =1, MA=1,

PC

=1, S =6, S =0, X =0, OP=0,

X 2 1 2 CI

R =1, W =1,

A PC

Z=2, MRD=1

trasferimento in R0:

MA=1, =1 , d =1, W=1

Z=2, MRD=1, X R 0 © 2016

Architettura degli Elaboratori

Struttura del processore PD32 19

MOVL X, R0

fetch: 24

=1, MA=1,

R PC

Z=2, MRD=1, W =1,

IR

=1, S =6, S =0, X =0, OP=0,

X 2 1 2 CI

R =1, W =1

A PC

indirizzo di X:

=1, MA=1,

R PC

X =1, S =6, S =0, X =0, OP=0,

2 1 2 CI

=1, W =1,

R A PC

Z=2, MRD=1

trasferimento in R0:

MA=1, =1 , d =1, W=1

Z=2, MRD=1, X R 0 © 2016

Architettura degli Elaboratori

Esecuzione delle istruzioni nel PD32 - 2 20

24

© 2016

Architettura degli Elaboratori

Struttura del processore PD32 21

ADDL Y, R0

fetch: 24

=1, MA=1,

R PC

Z=2, MRD=1, W =1,

IR

=1, S =6, S =0, X =0, OP=0,

X 2 1 2 CI

R =1, W =1

A PC

indirizzo di Y:

=1, MA=1,

R PC

X =1, S =6, S =0, X =0, OP=0,

2 1 2 CI

=1, W =1,

R A PC

Z=2, MRD=1

somma di Y con R0:

MA=1, =0,

Z=2, MRD=1, X 1

=1 , d =1, X =0,

Z=2, R 2 0 2

S =0, S =0, X =0, OP=0, X =0,

1 2 CI CO

W =1, X =1, W =1, X =0, W=1

C S SR R © 2016

Architettura degli Elaboratori

Esecuzione delle istruzioni nel PD32 - 3 22

24

© 2016

Architettura degli Elaboratori

Struttura del processore PD32 23

MOVL R0, Z

fetch: 24

=1, MA=1,

R PC

Z=2, MRD=1, W =1,

IR

=1, S =6, S =0, X =0, OP=0,

X 2 1 2 CI

R =1, W =1

A PC

indirizzo di Z:

=1, MA=1,

R PC

X =1, S =6, S =0, X =0, OP=0,

2 1 2 CI

=1, W =1,

R A PC

Z=2, MRD=1

scrittura di Z:

Z=2, MA=1, R =1,

1

s =1, R =1, MWR=1

0 R © 2016

Architettura degli Elaboratori

Struttura del processore PD32 24

MOVL R0, Z

fetch: 24

R =1, MA=1,

PC

Z=2, MRD=1, W =1,

IR

=1, S =6, S =0, X =0, OP=0,

X 2 1 2 CI

=1, W =1

R A PC

indirizzo di Z:

R =1, MA=1,

PC

=1, S =6, S =0, X =0, OP=0,

X 2 1 2 CI

R =1, W =1,

A PC

Z=2, MRD=1

scrittura di Z:

Z=2, MA=1, R =1,

1

s =1, R =1, MWR=1

0 R © 2016

Architettura degli Elaboratori Fine

01.e Il processore PD32

Testo di rif.to:

[Congiu] - 3.6, 3.8 (pg. 112–119)

Le istruzioni del PD32

01.f Classi di istruzioni

Programmazione dei protocolli di I/O

Struttura del processore PD32 1

17

© 2016

Architettura degli Elaboratori

Classi di istruzioni del PD32 2

Le istruzioni che il PD32 è in grado di

decodificare ed eseguire (istruzioni di macchina) 17

sono le seguenti:

● Istruzioni di trasferimento dei dati

● Istruzioni aritmetiche e logiche

● Istruzioni di controllo del programma

● Istruzioni di ingresso e uscita

Sono esaminate alcune istruzioni di ogni classe.

L’elenco completo delle istruzioni del PD32 si

trova nell’appendice B del libro di testo. © 2016

Architettura degli Elaboratori

Istruzioni di trasferimento dati (1 di 2) 3

MOVL s, d ;copia di un long-word (32 bit)

s: operando sorgente 17

d: operando destinazione

‘s’ e ‘d’ possono essere o indirizzi di registri (R0, …, R7)

oppure indirizzi di memoria.

MOVW s, d ;copia di un word (16 bit)

MOVB s, d ;copia di un byte (8 bit)

• se ‘s’ o ‘d’ rappresentano un registro di CPU, il word o il

byte interessati sono quelli meno significativi

• se ‘d’ rappresenta un registro di CPU, il bit di segno del

risultato (byte o word) viene esteso all’intero registro

© 2016

Architettura degli Elaboratori

Istruzioni di trasferimento dati (2 di 2) 4

ESEMPI: 17

; R0 R1

MOVL R0, R1 ®

; ext32(B[$2000]) R0

MOVB $2000, R0 ®

; R1 W[$2000]

MOVW R1, $2000 ®

W

; B[$2000] B[$3000]

MOVB $2000, $3000 ® © 2016

Architettura degli Elaboratori

Istruzioni aritmetiche e logiche (1 di 3) 5

opcode s, r (r indica uno dei registri R0, …, R7)

s, r ; somma: r + s r

ADDz ® 17

SUBz s, r ; sottrazione: r - s r

®

CMPz s, r ; confronto: imposta CNZV in funzione di r-s

NEGz s, r ; complemento a due: -s r

®

ANDz s, r ; funzione logica AND bit per bit

ORz s, r ; funzione logica OR bit per bit

XORz s, r ; funzione logica OR esclusivo bit per bit

NOTz s, r ; funzione logica NOT bit per bit

UMULs, r ; moltiplicazione su operandi usigned

SMUL s, r ; moltiplicazione su operandi signed

UDIV s, r ; divisione su operandi usigned

SDIV s, r ; divisione su operandi signed © 2016

Architettura degli Elaboratori

Istruzioni aritmetiche e logiche (2 di 3) 6

Operazioni di scorrimento:

opcode k, r 17

registro (R0, …, R7) contenente l’operando su cui vengono

r effettuate le operazioni di scorrimento.

numero di posizioni che vengono scorse.

k k, r ; scorrimento aritmetico verso sinistra

ASLz k, r ; scorrimento aritmetico verso destra

ASRz k, r ; scorrimento logico verso sinistra

LSLz k, r ; scorrimento logico verso destra

LSRz

• l’operando destinazione delle istruzioni aritmetiche e

logiche è sempre un registro dell’ALU;

• se z=B (o z=W), viene modificato solo il Byte (o il Word)

meno significativo del registro di destinazione © 2016

Architettura degli Elaboratori

Istruzioni aritmetiche e logiche (3 di 3) 7

ESEMPI: 17

; R0 + R1 R0

ADDL R1, R0 ®

R1 - W[$2000] R1

SUBW $2000, R1; ®

W W

; R0 & R1. R1

ANDB R0, R1 ®

B B B

; R2 * 8 R2

ASLW 3, R2 ®

W W © 2016

Architettura degli Elaboratori

Istruzioni di controllo 8

Istruzione di salto incondizionato:

JMP addr Go to 17

If

Istruzione di salto condizionato:

Jc addr

JNc addr

▪ c rappresenta uno dei bit di condizione,

▪ addr rappresenta un indirizzo di memoria.

L’esecuzione di queste istruzioni comporta l’inserimento

di addr nel PC (condizionato nel caso di Jc e di JNc). © 2016

Architettura degli Elaboratori

Esempi di Istruzioni di controllo 9

17

; $300 PC

JMP $300 ®

; IF Z=0 THEN $300 PC

JNZ $300 ®

; IF N=1 THEN $300 PC

JN $300 ® © 2016

Architettura degli Elaboratori

Altre istruzioni di controllo 10

Chiamata a subroutine: 17

JSR addr

Ritorno da subroutine:

RET

ESEMPI: ;PC push, $2400 PC

JSR $2400 ® ®

;pop PC

RET ® © 2016

Architettura degli Elaboratori

Istruzioni di input/output 11

Per realizzare i protocolli di e di descritti in

input output

precedenza, è sufficiente che il processore sia in grado di 17

eseguire le seguenti istruzioni:

disp, d

INz s, disp

OUTz disp

START disp, addr

JR disp, addr

JNR

se la destinazione dell’istruzione INz è un registro dell’ALU

e se z=B (o z=W), viene modificato solo il Byte (o il Word)

meno significativo del registro di destinazione © 2016

Architettura degli Elaboratori

Esempi di Istruzioni di input/output 12

; 5 linee di I/O indirizzi,

INB 5, R0 ® 17

IORD,

; invio del segnale

; linee I/O dati R0 .

® B

; 5 linee di I/O indirizzi,

START 5 ®

; invio del segnale START.

; 5 linee di I/O indirizzi,

JR 5, $200 ®

READY=1 THEN $200 PC

; IF ®

© 2016

Architettura degli Elaboratori

Protocollo di input: richiamo 13

17

PROTOCOLLO:

READY[DI] = ?

DI 0: aspetta e riesamina

1: START[DI] = 1

.

.

.

READY[DI] = ?

0: aspetta e riesamina

1: IORD[DI] = 1 © 2016

Architettura degli Elaboratori

Protocollo di input: programmazione 14

17

WAIT1: JNR DI, WAIT1 ;esame stato DI (ciclo

;di attesa: busy-wait)

START DI ;avvio dell’operazione

;di produzione del dato

WAIT2: JNR DI, WAIT2 ;esame stato DI

INB DI, R0 ;trasferimento del dato

© 2016

Architettura degli Elaboratori

Protocollo di input: diagramma temporale 15

17

DI © 2016

Architettura degli Elaboratori

Protocollo di output: richiamo 16

17

PROTOCOLLO:

READY[DO] = ?

DO 0: aspetta e riesamina

1: IOWR[DO] = 1

START[DO] = 1

READY[DO] = ?

0: aspetta e riesamina

1: output completato

© 2016

Architettura degli Elaboratori

Protocollo di output: programmazione 17

17

;esame stato DO:

W1: JNR DO, W1 ;trasferimento del dato

OUTB R0, DO ;avvio dell’operazione

START DO ;di consumo del dato

;esame stato DO:

W2: JNR DO, W2

... ;l’istruzione successiva

;sarà eseguita quando il

;dato sarà stato consumato

© 2016

Architettura degli Elaboratori Fine

01.f Le istruzioni del PD32

Testo di rif.to:

[Congiu] - 3.7,3.9,3.10 (pg. 112–127)

Modulo di Controllo

01.g L’esecuzione delle istruzioni

Realizzazione del modulo

Microprogrammazione

Esecuzione delle istruzioni 1

Istruzione di un linguaggio di alto livello:

Z := X + Y 14

(nel linguaggio assembly i nomi delle variabili X, Y, Z

possono essere usati per rappresentare indirizzi di

memoria)

Il PD32 non è in grado di sommare due operandi in

memoria (almeno uno deve essere in un registro dell’ALU).

L’istruzione di assegnazione va quindi espansa nella

sequenza di istruzioni macchina:

MOVL X, R0

ADDL Y, R0

MOVL R0, Z © 2016

Architettura degli Elaboratori

Codifica delle istruzioni nel PD32 2

14

dati Organizzazione dei dati e

delle istruzioni in memoria

istruzioni © 2016

Architettura degli Elaboratori

Esecuzione delle istruzioni nel PD32 - 1 3

14

© 2016

Architettura degli Elaboratori

Esecuzione delle istruzioni nel PD32 - 2 4

14

© 2016

Architettura degli Elaboratori

Esecuzione delle istruzioni nel PD32 - 3 5

14

© 2016

Architettura degli Elaboratori

Realizzazione del Modulo di controllo 6

14

Modulo di controllo

del processore PD32 © 2016

Architettura degli Elaboratori

Cosa fanno i segnali di controllo 7

14

Operazioni elementari eseguite dai segnali di controllo © 2016

Architettura degli Elaboratori

Modulo di controllo (variante) 8

14

Una possibile variante

PLA del Modulo di

Controllo del PD32 © 2016

Architettura degli Elaboratori

Modulo di controllo a microcodice 9

14

Una realizzazione

microprogrammata

del Modulo di

Controllo del PD32 © 2016

Architettura degli Elaboratori orizzontale/verticale

μ-programmazione 10

ciascun bit nella µ-istruzione corrisponde

Orizzontale:

ad un segnale di controllo: 14

µ-istruzioni lunghe: ad es µ-istruzioni da 80 bit se ci

● sono 80 segnali di controllo.

i campi della µ-istruzione contengono, in

Verticale:

forma codificata, i valori di più segnali di controllo (ad

es, se di 8 segnali uno solo può valere 1, bastano 3 bit);

µ-istruzioni corte: ad es µ-istruzioni da 20 bit;

● minor area di silicio;

● ®

ma è necessaria la decodifica minor velocità.

● ®

soluzione mista.

A due livelli: © 2016

Architettura degli Elaboratori a due livelli

μ-programmazione 11

la nano-ROM contiene (una sola copia di) tutte

n-ROM:

le µ-istruzioni orizzontali. 14

la micro-ROM, anziché contenere sequenze di

μ-ROM:

µ-istruzioni orizzontali, contiene sequenze di puntatori

(meno bit) alle µ-istruzioni nella n-ROM;

esempio:

le µ-istruzioni orizzontali di un processore siano da 120 bit;

● il numero µ-istruzioni orizzontali diverse sia inferiore a 512;

allora la µ-ROM contiene sequenze di elementi da 9 bit (puntatori

alle µ-istruzioni orizzontali nella n-ROM), anziché sequenze di

elementi da 120 bit.

minor area di silicio;

® minor velocità.

ma sono richiesti 2 accessi ® © 2016

Architettura degli Elaboratori

Livelli di programmazione - 1 12

14

Notazioni diverse del medesimo programma © 2016

Architettura degli Elaboratori

Livelli di programmazione - 2 13

14

Operazioni di traduzione e di esecuzione © 2016

Architettura degli Elaboratori

Livelli di programmazione - 3 14

14

© 2016

Architettura degli Elaboratori Fine

01.g Modulo di Controllo

Esercitazioni 1

T1.1 Rappresentazione delle informazioniM

Memoria

ALU

Architettura PD32

Esercizio 1 1

!" 14

! ! # $ % & '

$ % & ' !

% % %

% &

& #

$ % &

( ))) *+& ,#

/0 1 ' 2

/0 1 !

2

/0 1 & & '

2 © 2012

Architettura degli Elaboratori

Soluzione 1 2

S2

S1 14

ultimo primo

$300 $400

$10 $10

$3C $B0 $20 $10

$301 $401

$20 $20

$302 $402

$B0 $B0

$303 $403

$3C $3C

byte byte

Big endian Little endian

$3CB02010 long word

$1020B03C long word © 2012

Architettura degli Elaboratori

Soluzione 1 (2) 3

positivo

S2 $3CB02010 long word 14

%0 01111001 0110 0000 0100 0000 0010 000

$400 $10 /2 /10 /19

$401 $20 /3

$402 $B0 121 = e(/6, 127)

$403 $3C

byte

Little endian /6

$1.604020 * 2 =

val = + /2 /3 /10 /19 /6

= + (1.0 + 2 + 2 + 2 + 2 ) * 2 ≈ /6

+ (1.0 + 0.25 + 0.125 + 0.001 + 0.000002) * 2 =

≈ /6

= + 1.376002 * 2 ≈ © 2012

Architettura degli Elaboratori /2

+ 2.15 * 10

Esercizio 2 4

Si voglia realizzare una memoria statica

da 128 Kbyte mediante n banchi ciascuno

14

ciascuno composto da 8 chip di memoria

da 4Kx1 bit.

/Quanto deve valere n?

/Quali bit dell’indirizzo selezionano il

linee di

banco da attivare?Quante

/Quante linee di indirizzo devono

pervenire come indirizzo di selezione del

bit a ciascun chip? © 2012

Architettura degli Elaboratori

Soluzione 2 5

Ogni banco fornisce 4Kbyte di memoria,

per cui risulta:n = 128Kbyte 14

17 12 5

n = 128Kbyte / 4Kbyte = 2 / 2 = 2

= 32

Per indirizzare 128Kbyte sono necessarie

17 linee di indirizzo di cui 5 servono per

ip

l’atti

selezionare il banco (attraverso

select ) e 12 per indirizzare in ciascun

chip uno dei 4Kbit in esso presenti. © 2012

Architettura degli Elaboratori

Esercizio 3 6

In una memoria dinamica da 64 Kbit x

1, organizzata come una matrice quadrata

14

quadrata di bit, la lettura di una cella di

memoria richiede ta=50 ns. Calcolare

qual è il minimo periodo di refresh di

ciascun bit tale per cui l’impegno ref

percentuale degli accessi dedicati al

superiore allo 0.5%. © 2012

Architettura degli Elaboratori

Soluzione 3 7

Essendo la matrice di bit quadrata,

risulta: 14

nRighe = nColonne = sqrt(64K) = 256

ta / (tr /nRighe) 0.005

tr ≥ 50*10/9 * 256 / 0.005 = 2.56 ms

© 2012

Architettura degli Elaboratori

Esercizio 4 8

Facendo uso del registro TEMP si indichi la

sequenza di segnali che l’unità di controllo del 14

PD32 deve generare per realizzare

l’istruzione:

ADANDL $2000, R3

che effettua le seguenti operazioni:

R3 /> TEMP

L[$2000]+R3 /> R3

TEMP && R3 /> R3

Successivamente si ipotizzi una opportuna

codifica dell’istruzione. © 2012

Architettura degli Elaboratori

Struttura del processore PD32 9

14

© 2012

Architettura degli Elaboratori

Accesso ai registri dell’ALU 10

14

© 2012

Architettura degli Elaboratori

Modulo ALU 11

14

© 2012

Architettura degli Elaboratori

Soluzione 4 12

Realizzazione dell’istruzione ADANDL $2000, R3

Dopo le sequenze di segnali (qui non riportate) che realizzano i fetch del long word operativo e

di quello d’estensione (contenente l’indirizzo del primo operando), i segnali richiesti sono: 14

; $2000 è in MBR

; R3 /> TEMP

s =1 , R =1, R =1, W =1

3 1 R T

; L[$2000]+R3 /> R3

MA=1, Z=2, MRD=1, X =0

1

=1, d =1, X =0, S =0, S =0, X =0, OP=0, X =0, W =1, X =0, W=1

Z=2, R 2 3 2 1 2 CI CO C R

; TEMP && R3 /> R3

Z=2, R =1, X =0, R =1, d =1, X =0, S =0, S =0, OP=2, X =1, X =0, W =1, W=1

T 1 2 3 2 1 2 S R SR

L’istruzione potrebbe essere inserita nella classe delle istruzioni logiche, quindi potrebbe avere

il formato di quella classe di istruzioni qui riassunto:

3 2 2 2 2 1 1 1 1 1 1 0 0 0 0 0 0 0

1 9 8 4 3 6 5 4 3 2 1 9 8 6 5 3 2 0

+-----+---------+---------------+---+---+-----+-----+-----+-----+

| 011 | I | ===== | = | z | S.M.| S.R.| 000 | D.R.|

+-----+---------+---------------+---+---+-----+-----+-----+-----+

All’istruzione ADANDz potrebbe corrispondere il codice 4 (00100) nel campo I, essendo i

valori di I da 0 a 3 già riservati alle attuali 4 istruzioni logiche © 2012

Architettura degli Elaboratori

Esercizio 5 13

Supponendo che nella memoria del PD32 sia:

L[$2000] = $AABBCCDD 14

L[$2004] = $11223344

e che vengano eseguite le tre seguenti

istruzioni:

MOVW $2002, R0

RCRW 2, R0

MOVB R0, $2005

dire cosa contengono alla fine R0 e i due

longword di memoria © 2012

Architettura degli Elaboratori

Soluzione 5 14

Il PD32 adotta l’organizzazione ‘little endian’, pertanto l’istruzione:

MOVW $2002, R0

carica nel word meno significativo di R0, e lo estende con segno su 32 bit, il 14

word più significativo del long word all’indirizzo $2000, cioè $AABB, pertanto con

estensione di segno negativo:

R0 = $FFFFAABB

L’istruzione:

RCRW 2, R0

effettua 2 rotazioni a destra di un posto, ciascuna della quali provoca l’ingresso

del corrente bit C come nuovo bit 15, lo shift a destra del word meno

significativo di R0 (quello più significativo rimane inalterato), l’uscita del corrente

bit 0 come nuovo valore del bit C. Ovvero:

R0 = $FFFFAABB C=0 (è il valore lasciato dalla precedente istruzione MOV)

dopo il primo RCRW, R0 = $FFFF555D C=1

dopo il secondo RCRW, R0 = $FFFFAAAE C=1

L’istruzione:

MOVB R0, $2005

copia il LSBy di R0 (cioè $AE) nel byte di indirizzo $2005, quindi alla fine i

valori d’interesse sono:

R0 = $FFFFAAAE C=0 N=1 Z=0 V=0

L[$2000] = $AABBCCDD

L[$2004] = $1122AE44 © 2012

Architettura degli Elaboratori Fine

T1.1 Esercitazioni 1

ADDL Y, R0

fetch:

X2=1, Z=2,

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1

RPC=1, MA=1,

MRD=1, WIR=1,

indirizzo di Y:

X2=1, Z=2,

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1

RPC=1, MA=1,

MRD=1, WIR=1,

indirizzo di Y:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1

RPC=1, MA=1,

MRD=1, WIR=1,

indirizzo di Y:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1,

RPC=1, MA=1,

MRD=1, WPC=1

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1

RPC=1, MA=1,

MRD=1, WIR=1,

indirizzo di Y:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1,

RPC=1, MA=1,

MRD=1, WPC=1

somma di Y con R0:

RPC=1, MA=1, Z=2,

MRD=1, Z=2,

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1

RPC=1, MA=1,

MRD=1, WIR=1,

indirizzo di Y:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1,

RPC=1, MA=1,

MRD=1, WPC=1

somma di Y con R0:

RPC=1, MA=1, Z=2,

MRD=1, Z=2,

R2=1 , d0=1,

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1

RPC=1, MA=1,

MRD=1, WIR=1,

indirizzo di Y:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1,

RPC=1, MA=1,

MRD=1, WPC=1

somma di Y con R0:

RPC=1, MA=1, Z=2,

MRD=1, Z=2,

R2=1 , d0=1,

X2=0, X1=0, OP=0,

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1

RPC=1, MA=1,

MRD=1, WIR=1,

indirizzo di Y:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1,

RPC=1, MA=1,

MRD=1, WPC=1

somma di Y con R0:

RPC=1, MA=1, Z=2,

MRD=1, Z=2,

R2=1 , d0=1,

X2=0, X1=0, OP=0,

S1=0, S2=0, XCI=0, OP=0

XCO=0, WC=1,

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1

RPC=1, MA=1,

MRD=1, WIR=1,

indirizzo di Y:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1,

RPC=1, MA=1,

MRD=1, WPC=1

somma di Y con R0:

RPC=1, MA=1, Z=2,

MRD=1, Z=2,

R2=1 , d0=1,

X2=0, X1=0, OP=0,

S1=0, S2=0, XCI=0, OP=0

XCO=0, WC=1,

XR=0, XS=1, WSR=1, W=1, d0=1

ADDL Y, R0

fetch:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1

RPC=1, MA=1,

MRD=1, WIR=1,

indirizzo di Y:

X2=1, Z=2,

S1=6, S2=0, XCI=0, OP=0,

RA=1, WPC=1,

RPC=1, MA=1,

MRD=1, WPC=1

somma di Y con R0:

RPC=1, MA=1, Z=2,

MRD=1, Z=2,

R2=1 , d0=1,

X2=0, X1=0, OP=0,

S1=0, S2=0, XCI=0, OP=0

XCO=0, WC=1, W=1, d0=1

XR=0, XS=1, WSR=1,

Testo di rif.to:

[Congiu] - 4.1,4.2 (pg. 129–138)

Le istruzioni di macchina

02.a Classificazione delle istruzioni

Direttive per l’assemblatore

Classificazione delle istruzioni 1

È possibile classificare le istruzioni di macchina

in base al numero degli a cui si

operandi 15

riferiscono (il termine ‘operando’ è qui usato in

senso lato e comprende anche il risultato).

Questa classificazione può essere usata per

classificare anche i processori:

tre indirizzi

● Macchine a

● Macchine a due indirizzi

● Macchine a un indirizzo

● Macchine a zero indirizzi © 2016

Architettura degli Elaboratori

Macchine a tre indirizzi 2

ADD X, Y, Z ; M[X] + M[Y] M[Z]

® 15

SUB X, Y, Z ; M[X] - M[Y] M[Z]

®

MUL X, Y, Z ; M[X] * M[Y] M[Z]

®

DIV X, Y, Z ; M[X] / M[Y] M[Z]

®

(si noti l’ordine degli operandi nelle operazioni

non invertibili, sottrazione e divisione) © 2016

Architettura degli Elaboratori

Macchine a tre indirizzi - esempio 3

Espansione di una istruzione HLL (High Level 15

Language) che valuta una espressione aritmetica:

Z := U * (V - (W + X) / Y)

ADD W, X, T

DIV T, Y, T

SUB V, T, T

MUL U, T, Z istruzioni di macchina

4 © 2016

Architettura degli Elaboratori

Macchine a due indirizzi 4

ADD X, Y ; M[X] + M[Y] M[Y]

® 15

SUB X, Y ; M[X] - M[Y] M[Y]

®

MUL X, Y ; M[X] * M[Y] M[Y]

®

DIV X, Y ; M[X] / M[Y] M[Y]

®

Serve anche un’istruzione che consenta di

spostare a destinazione il risultato finale:

MOV X, Y ; M[X] M[Y]

® © 2016

Architettura degli Elaboratori

Macchine a due indirizzi – esempio 1 5

Espansione della stessa istruzione HLL:

Z := U * (V - (W + X) / Y) 15

ADD W, X

DIV X, Y

SUB V, Y

MUL U, Y

MOV Y, Z istruzioni di macchina

5

(ma i valori originari di X e Y vengono persi) © 2016

Architettura degli Elaboratori

Macchine a due indirizzi – esempio 2 6

Se si vogliono conservare tutti gli operandi:

Z := U * (V - (W + X) / Y) 15

MOV X, T

ADD W, T

MOV Y, Z

DIV T, Z

SUB V, Z

MUL U, Z 6 istruzioni di macchina

© 2016

Architettura degli Elaboratori

Macchine ad un indirizzo 7

Un operando è nel registro accumulatore (RA) 15

ADD X ; RA + M[X] RA

®

SUB X ; RA - M[X] RA

®

MUL X ; RA * M[X] RA

®

DIV X ; RA / M[X] RA

®

Servono anche due istruzioni per copiare un

operando da o verso RA:

LOAD X ; M[X] RA

®

STORE X ; RA M[X]

® © 2016

Architettura degli Elaboratori

Macchine ad un indirizzo – esempio 8

Z := U * (V - (W + X) / Y) 15

LOAD W

ADD X

DIV Y

STORE T

LOAD V

SUB T

MUL U

STORE Z 8 istruzioni di macchina © 2016

Architettura degli Elaboratori

Macchine a zero indirizzi 9

stack

Gli operandi nello 15

D push ;SP - 2 SP, D W[SP]

® ® ®

pop D ;W[SP] D, SP + 2 SP

® ® ®

;si suppone che D sia un word (2 byte)

© 2016

Architettura degli Elaboratori

Macchine a zero indirizzi (con stack) 10

ADD ; pop + pop push

® 15

SUB ; pop T, pop - T push

® ®

MUL ; pop * pop push

®

DIV ; pop T, pop / T push

® ®

Servono due istruzioni per estrarre o inserire

un operando in cima allo stack:

POP X ; pop M[X]

®

PUSH X ; M[X] push

® © 2016

Architettura degli Elaboratori

Macchine a zero indirizzi – esempio 11

Z := U * (V - (W + X) / Y) 15

PUSH U

PUSH V

PUSH W

PUSH X

ADD

PUSH Y

DIV

SUB

MUL Z

POP 10 istruzioni di macchina

© 2016

Architettura degli Elaboratori

Notazione polacca inversa 12

Z := U * (V - (W + X) / Y) 15

L’espansione della espressione

PUSH U aritmetica in istruzioni a zero

PUSH V indirizzi corrisponde alla

PUSH W riscrittura della espressione con

operatori postfissi, secondo la

PUSH X notazione polacca inversa

ADD Reverse Polish Notation, RPN

( ):

Y

PUSH

DIV + Y / - *

U V W X

SUB

MUL

POP Z 10 istruzioni di macchina

© 2016

Architettura degli Elaboratori

Direttive per l’assemblatore - 1 13

Specificano operazioni che devono essere eseguite

dall’assemblatore. 15

direttive per la DEFINIZIONE DI SIMBOLI

1. direttiva LABEL ; il simbolo rappresenta

WAIT1: JNR DI, WAIT1 ; un indirizzo di memoria

2. direttiva di ASSEGNAZIONE

; il simbolo rappresenta un valore generico

AD1 = 24 ; che di solito non è un indirizzo di memoria

© 2016

Architettura degli Elaboratori

Direttive per l’assemblatore - 2 14

direttive per la

DEFINIZIONE DI AREE DI MEMORIA 15

espressione

.DS ; l’assemblatore calcola il valore N

z ; della espressione e lascia libera

; un’area di memoria di dimensione

; pari a N byte (o word o long-word).

esp esp esp

, ,… ; l’assemblatore calcola N = e

.DC z 1 2 i

i

; inserisce in memoria i valori N , N ,...

1 2

‘stringa‘,0

.DCB ; l’assemblatore inserisce in

; memoria, in byte consecutivi,

; i codici ASCII della stringa di

; caratteri. © 2016

Architettura degli Elaboratori

Direttive per l’assemblatore - 3 15

direttive per la

DEFINIZIONE DI SEGMENTI DI MEMORIA 15

.TEXT ; indica l’inizio di un segmento contenente

; codice (istruzioni)

.DATA ; indica l’inizio di un segmento contenente

; dati inizializzati

.BSS ; indica l’inizio di un segmento contenente

; dati non inizializzati © 2016

Architettura degli Elaboratori Fine

02.a Le istruzioni di macchina

Testo di rif.to:

[Congiu] – 4.3 (pg. 138–148)

Metodi di indirizzamento

02.b Indirizzamento immediato

Indirizzamento di registro

Indirizzamenti in memoria

Metodi di indirizzamento – 1 1

Gli indirizzi degli operandi sono collocati in

campi (gruppi di bit) delle istruzioni.

appositi 26

Esempio:

Il modo di considerare il contenuto del

campo INDIRIZZO determina il particolare

metodo di indirizzamento. © 2016

Architettura degli Elaboratori

Metodi di indirizzamento – 2 2

In genere il primo word (operation di

word)

ciascuna istruzione contiene, oltre alla codifica 26

dell’operazione da eseguire, le informazioni

relative ai metodi di indirizzamento da

utilizzare per accedere agli operandi.

Alcuni di questi metodi richiedono ulteriori

informazioni che vengono memorizzate in uno o

più word aggiuntivi (extension word). © 2016

Architettura degli Elaboratori

Metodi di indirizzamento nel PD32 3

Nel PD32 le istruzioni hanno un operation long-word

(OL) di 32 bit. 26

Alcuni metodi di indirizzamento richiedono informazioni

contenute in un extension long-word (EL) di 32 bit.

Ogni indirizzo (IND1, IND2) è specificato da due campi:

M (da 3 bit) che individua il modo di indirizzamento,

● R (da 3 bit) che individua l’eventuale registro usato.

● Codifica dei modi di

indirizzamento nelle

istruzioni del PD32

© 2016

Architettura degli Elaboratori

Metodi di indirizzamento usati 4

Indirizzamento immediato

Assoluto diretto 26

in blu i metodi non presenti nel PD32

Assoluto indiretto (attribuibili al PD132)

Diretto di registro

Indiretto con registro indiretto

e )

Auto-incrementante (diretto indiretto

Auto-decrementante (diretto e )

Con registro indice

Indiretto con registro indice

Con registro base indiretto

Auto-relativo (diretto e ) © 2016

Architettura degli Elaboratori

Indirizzamento immediato 5

; 28 R0

MOVL #28, R0 ® 26

PD32 l’indirizzamento immediato è individuato dal

Nel

valore 1 nel campo M. Il campo R non è usato.

immediato è contenuto in un EL di 32 bit.

L’operando 31 31

Il suo valore è compreso tra -2 e 2 -1.

Per accedere all’operando il processore deve eseguire il

fetch di questo EL. fetch(OL) fetch(EL)

Numero accessi alla memoria: + +0

fetch(OL) + 1 = 2 © 2016

Architettura degli Elaboratori

Indirizzamento assoluto 6

; L[132] + R0 R0

ADDL 132, R0 ® 26

PD32 l’indirizzamento assoluto corrisponde al valore

Nel

2 nel campo M. Il campo R non è usato.

L’indirizzo assoluto è contenuto in un EL di 32 bit.

32 = 4 GB di memoria.

Consente perciò di accedere a 2

Per accedere all’operando il processore, dopo aver

fetch

effettuato il dell’EL, con cui ottiene l’indirizzo

dell’operando, deve effettuare un ulteriore accesso alla

memoria (al valore dell’operando).

fetch(OL) fetch(EL)

Numero accessi alla memoria: + +1

fetch(OL) + 2 = 3 © 2016

Architettura degli Elaboratori

Indirizzamento assoluto indiretto (PD132) 7

; L[L[456]] + R0 R0

ADDL @456, R0 ®

Nel PD132 l’indirizzo del puntatore è contenuto in un EL 26

30

di 32 bit, con cui si possono individuare 2 = 1 G

puntatori (da 4 byte) situati in memoria.

32

Ciascun puntatore può accedere a 2 = 4 GB.

Per accedere all’operando il processore, dopo aver

fetch dell’EL, con cui ottiene l’indirizzo di

effettuato il

un puntatore all’operando, deve effettuare due ulteriori

accessi alla memoria:

il primo per leggere il puntatore all’operando,

● il secondo per accedere al valore dell’operando

● fetch(OL) fetch(EL)

Numero accessi alla memoria: + + 2

fetch(OL) + 3 = 4 © 2016

Architettura degli Elaboratori

Confronto tra i tre metodi presentati 8

26

Confronto tra i 3 diversi modi di indirizzamento © 2016

Architettura degli Elaboratori

Indirizzamento diretto di registro 9

ADDL R0, R1 ; R0 + R1 R1

® 26

Nel PD32 l’indirizzamento diretto di registro

corrisponde al valore 0 nel campo M.

Il campo R specifica il registro in cui si trova l’operando.

Per accedere all’operando non sono necessari accessi alla

memoria. fetch(OL)

Numero accessi alla memoria: + 0

fetch(OL) + 0 = 1 © 2016

Architettura degli Elaboratori

Indirizzamento indiretto con registro 10

Uguale all'indiretto di

memroia ; L[R0] + R1 R1

ADDL (R0), R1 ® 26

Nel PD32 l’indirizzamento indiretto con registro

corrisponde al valore 3 nel campo M.

Il campo R specifica il registro in cui si trova un

puntatore all’operando.

Per accedere all’operando è necessario un accesso alla

memoria (all’indirizzo contenuto nel registro specificato).

fetch(OL) + 1

Numero accessi alla memoria: fetch(OL) + 1 = 2 © 2016

Architettura degli Elaboratori

Indirizzamento auto-incrementante 11

; M[R0] + R1 R1

ADDz (R0)+, R1 ®

; R0 + d R0

® 26

PD32 questo indirizzamento è individuato dal valore 7

Nel

nel campo M. Il campo R specifica il registro in cui si trova

un puntatore all’operando (è un indirizzamento indiretto

con registro).

Dopo l’accesso all’operando, il puntatore viene incrementato

di una quantità d pari alla lunghezza (in byte) dell’operando

stesso (d = 1 per B, d = 2 per W, d = 4 per L).

Per accedere all’operando è necessario un accesso alla

memoria (all’indirizzo contenuto nel registro specificato).

fetch(OL) + 1

Numero accessi alla memoria: fetch(OL) + 1 = 2 © 2016

Architettura degli Elaboratori

Indirizzamento auto-decrementante 12

; R0 - d R0

ADDz -(R0), R1 ®

; M[R0] + R1 R1

® 26

PD32 questo indirizzamento è individuato dal valore 6

Nel

nel campo M. Il campo R specifica il registro in cui si trova

un puntatore all’operando (è un indirizzamento indiretto

con registro).

Prima di accedere all’operando, il puntatore viene

decrementato di una quantità d pari alla lunghezza (in byte)

dell’operando (d = 1 per B, d = 2 per W, d = 4 per L).

Per accedere all’operando è necessario un accesso alla

memoria (all’indirizzo contenuto nel registro specificato).

fetch(OL) + 1

Numero accessi alla memoria: fetch(OL) + 1 = 2 © 2016

Architettura degli Elaboratori

Utilità dell’auto-in(de)cremento 13

Consente di percorrere liste di dati consecutivi (in avanti

o a ritroso). 26

Consente di realizzare gli accessi LIFO ad uno stack:

MOVW 1000, -(R7) ; W[1000] push

®

MOVW (R7)+, R0 ; pop RO

®

; (R7 funge da stack pointer)

© 2016

Architettura degli Elaboratori

Indirizzamento autoinc. indiretto (PD132) 14

; W[L[R0]] + R1 R1

ADDW @(R0)+, R1 ®

W W 26

; R0 + 4 R0

®

Questo metodo non esiste nel PD32.

Il dato puntato dal registro specificato è un puntatore

(un indirizzo, lungo 4 byte), perciò l’incremento è di 4.

Dopo il fetch, il primo accesso alla memoria ottiene un

puntatore all’operando; un secondo accesso è necessario

per ottenere il valore dell’operando.

fetch(OL)

Numero accessi alla memoria: + 2

fetch(OL) + 2 = 3 © 2016

Architettura degli Elaboratori

Indirizzamento autodec. indiretto (PD132) 15

; R0 - 4 R0

ADDB @-(R0), R1 ® 26

; B[L[R0]] + R1 R1

®

B B

Questo metodo non esiste nel PD32.

Il dato puntato dal registro specificato è un puntatore

(un indirizzo, lungo 4 byte), perciò l’incremento è di 4.

Dopo il fetch, il primo accesso alla memoria ottiene un

puntatore all’operando; un secondo accesso è necessario

per ottenere il valore dell’operando.

fetch(OL) + 2

Numero accessi alla memoria: fetch(OL) + 2 = 3 © 2016

Architettura degli Elaboratori

Indirizzamento con registro indice - 1 16

E’ un metodo di indirizzamento a due componenti: 26

; L[X+R1] R2

MOVL X(R1), R2 ®

X: indirizzo base

R1: registro indice (contiene l’offset)

Nel PD32 questo metodo di indirizzamento è individuato

4 nel campo M.

dal valore

Il registro che funge da registro indice è specificato nel

R.

campo © 2016

Architettura degli Elaboratori

Indirizzamento con registro indice - 2 17

L’indirizzo base è contenuto in un EL.

X

Per accedere all’operando il processore, dopo aver 26

fetch

effettuato il dell’EL, con cui ottiene l’indirizzo

base, lo somma all’offset contenuto nel registro indice,

per calcolare l’indirizzo dell’operando; effettua poi un

ulteriore accesso alla memoria (al valore dell’operando).

fetch(OL) fetch(EL)

Numero accessi alla memoria: + +1

fetch(OL) + 2 = 3

Codifica, nel PD32,

dell’indirizzamento

con registro indice © 2016

Architettura degli Elaboratori

Indirizzamento con registro indice - 3 18

ESEMPIO DI USO DI UN REGISTRO INDICE:

short[] A, B, C; //array di short (2 byte) 26

for (int i=0; i<100 ; i++) A[i]=B[i]+C[i];

102

Organizzazione in memoria

dei tre array A,B,C © 2016

Architettura degli Elaboratori

Indirizzamento con registro indice - 4 19

La somma dei due array può essere effettuata

mediante le seguenti istruzioni: 26

(B[i])

;B[R1] R0

MOVW 300(R1), R0 →

;C[R1] + R0 R0 (B[i]+C[i])

ADDW 500(R1), R0 →

;R0 A[R1] (A[i])

MOVW R0, 100(R1) →

eseguite iterativamente 100 volte, con il registro R1

contenente il valore 0 la prima volta e incrementando

2 unità ad ogni iterazione.

questo valore di © 2016

Architettura degli Elaboratori

Indirizzamento con registro indice - 5 20

Organizzazione del ciclo iterativo che calcola la somma dei

due array: 26

MOVB #100, R2 ; valore iniziale del contatore

MOVL #0, R1 ; … e del registro indice

LOOP: MOVW 300(R1), R0

ADDW 500(R1), R0

MOVW R0, 100(R1)

ADDL #2, R1 ; incremento del registro indice

SUBB #1, R2 ; decremento del contatore

JNZ LOOP ; criterio di fine iterazioni

……. ……. ; istruzione successiva © 2016

Architettura degli Elaboratori

Indirizzamento indiretto con RI (PD132) 21

• Forma pre-indexed:

il registro indice RI viene usato prima di effettuare 26

l’indirizzamento indiretto: in tal modo il longword

X+RI viene interpretato come un

situato all’indirizzo

puntatore all’operando.

L’operando è M[L[X + RI]]

®

• Forma post-indexed:

il registro indice RI viene usato dopo aver considerato

l’indirizzo base X in modo indiretto: l’indirizzo

dell’operando si ottiene sommando il contenuto del

registro indice al contenuto del longword di memoria

situato all’indirizzo base.

+ RI]

L’operando è M[L[X]

® © 2016

Architettura degli Elaboratori

Confronto tra pre e post-indexed (PD132) 22

26

© 2016

Architettura degli Elaboratori

Indirizzamento con registro base (PD132) 23

L’indirizzo viene calcolato come somma del contenuto di

RB (il registro base) e di un offset D fornito

un registro

dall’istruzione. 26

L’operando è M[RB + D].

®

Alcune macchine ammettono sia l’indirizzamento con

registro base sia quello con registro indice. In tal caso

l’indirizzo dell’operando è dato dalla somma di tre

componenti:

RB (che contiene l’indirizzo base),

● X (che contiene un offset, specificato nella

● istruzione),

RI (che contiene un indice).

● L’operando è M[RB + X + RI]

® © 2016

Architettura degli Elaboratori

Indirizzamento autorelativo 24

E’ anch’esso un metodo di indirizzamento a due

componenti. L’indirizzo dell’operando è dato dalla somma 26

del contenuto del program counter PC e di un offset D.

PD32 l’indirizzamento auto-relativo è individuato dal

Nel

valore 5 nel campo M. Il campo R non è usato e l’offset D

è contenuto in un EL.

L’operando è M[PC + D].

®

Il valore del PC che interviene nella somma è quello

che punta al (primo) EL dell’istruzione. indiretto

Nel caso di indirizzamento auto-relativo

(PD132) la somma D + PC individua non l’operando ma un

puntatore ad esso. © 2016

Architettura degli Elaboratori

Indirizzamento autorelativo - esempio 25

istruzione di HLL:

if a > max then max := a 26

corrispondenti istruzioni PD32 (sia a in R1 e max in R0):

Indirizzi istruzioni commenti

Ind: CMP R0, R1 ; R1 - R0 (a - max)

JN +8(PC) ; salta se a – max < 0

(Ind+4) MOVL R1, R0

(Ind+12) ; max := a

(Ind+16) ... ; istruzione cui salta

Il valore del PC che interviene nella somma è quello

che punta al (primo) EL dell’istruzione stessa:

nell’esempio è Ind+8, quindi la destinazione del salto

è Ind+8+8=Ind+16. © 2016

Architettura degli Elaboratori

Modi di indirizzamento nel PD32 26

26

t © 2016

Architettura degli Elaboratori Fine

02.b Metodi di indirizzamento

Testo di rif.to:

[Congiu] – 4.4.1 (pg. 148–158)

Uso dei metodi di indirizzamento

02.e Un esempio: acquisizione dati

Esempi d’impiego

Confronto tra i metodi

Analisi temporale

Sistema di acquisizione dati 1

5 dispositivi A/D (convertitori analogico/digitale)

siano collegati ad un calcolatore come indicato in figura: 37

© 2015

Architettura degli Elaboratori

Sistema di acquisizione dati - esempio 2

Le conversioni A/D sono sincronizzate da un clock c(t). 37

Ciascun fronte di salita di avvia, in parallelo, le

c(t)

conversioni su tutti 5 i dispositivi: i 5 campioni (valori

) si riferiscono quindi al

digitali prodotti nei registri Ru i

medesimo istante.

Il processore deve acquisire i 5 campioni e ricopiarli in

vengano

memoria, prima che i valori contenuti nei Ru

i

sovrascritti dai nuovi campioni prodotti dal successivo

fronte di salita del clock (specifica real-time).

100 set di dati dai 5 convertitori A/D

Si debbano acquisire © 2015

Architettura degli Elaboratori

Conversione A/D 3

registro Ru da 16 bit: 64 K valori digitali possibili,

● l’errore (assoluto) di discretizzazione massimo è:

● 37

)/64K

= (S S

e -

s i i

MAX MIN

Errore di discretizzazione

nella conversione A/D: © 2015

Architettura degli Elaboratori

Interfaccia del dispositivo A/D 4

37

Ru

(16 bit) s(t)

A/D c(t) © 2015

Architettura degli Elaboratori

Sincronizzazione delle conversioni 5

Le conversioni vengono avviate dal primo fronte di salita del clock

successivo al comando START inviato dal processore. 37

Il tempo necessario al convertitore A/D per produrre il valore

digitale in Ru è (tempo di conversione).

t

c

Rispetto allo START, il dato convertito è pronto con un ritardo

minimo pari a e massimo pari a (T = periodo del clock).

t t +T

c c

Diagramma temporale

delle operazioni di

conversione © 2015

Architettura degli Elaboratori

Organizzazione dei dati in memoria 6

Organizzazione della struttura di dati nella

memoria centrale: 37

● a ciascun convertitore sia associata

un’area (a partire dagli indirizzi TAB1,

TAB2, …) destinata a contenere i dati

acquisiti;

● vi sia anche una tabella di puntatori,

IND, ciascuno dei

situata all’indirizzo

quali "punta al" (contiene l’indirizzo del)

primo elemento dell’area

corrispondente destinata a contenere i

dati.

● i puntatori (indirizzi di memoria) sono

da 4 byte; i dati (in TABi) da 2 byte.

© 2015

Architettura degli Elaboratori

Organizzazione dei dati in memoria 7

Direttive per definire l’organizzazione della

struttura di dati nella memoria centrale: 37

.BSS

TAB1: .DSW 100

TAB2: .DSW 100

TAB3: .DSW 100

TAB4: .DSW 100

TAB5: .DSW 100

...

.DATA

IND: .DCL TAB1, TAB2, TAB3, TAB4, TAB5

© 2015

Architettura degli Elaboratori

Programmazione dell’esempio 8

Conviene scrivere prima il codice che acquisisce

i 100 campioni da un convertitore (ad es. AD4). 37

Vengono ora presentate diverse soluzioni, con

diversi modi di indirizzamento (allo scopo di

esemplificarne l’uso e di consentire qualche

raffronto).

Si affronterà poi il problema di codificare la

soluzione completa, che acquisisce 100 set di 5

campioni simultanei dai 5 convertitori,

rispettando le specifiche di tempo reale. © 2015

Architettura degli Elaboratori

a

1 soluzione 9

Si supponga di usare una macchina (più semplice del PD32)

ad un indirizzo (con registro accumulatore), dotata dei

● soli metodi di indirizzamento: 37

▪ immediato,

▪ assoluto (diretto e indiretto);

in grado di eseguire almeno le seguenti istruzioni:

● m

- aritmetiche: ADD m

SUB m

- di trasferimento: LOAD(W) m

STORE(W) m

- di controllo: JNZ disp

- di I/O: INW disp

START disp m

JNR , © 2015

Architettura degli Elaboratori a

Codifica della 1 soluzione 10

PT: .DSL 1 ; puntatore

CT: .DSL 1 ; contatore

. . . 37

LOAD IND+12 ; valore iniziale del …

STORE PT ; … puntatore

LOAD #100 ; valore iniziale del …

STORE CT ; … contatore

LOOP: JNR AD4, LOOP ; protocollo di input per la …

LOOP1: START AD4 ; … acquisizione …

WAIT: JNR AD4, WAIT ; … del …

INW AD4 ; … dato

STOREW @PT ; memorizzazione del dato

LOAD PT ; incremento …

ADD #2 ; … del …

STORE PT ; puntatore

LOAD CT ; aggiornamento …

SUB #1 ; … del …

STORE CT ; … contatore

JNZ LOOP1 ; iterazione se L[CT] è diverso da zero © 2015

Architettura degli Elaboratori

a

2 soluzione 11

Si supponga di usare una macchina:

- con più registri e quindi con la possibilità di usare 37

con registro;

anche i metodi di indirizzamento

- i metodi di indirizzamento disponibili siano:

● immediato,

● assoluto (diretto),

● diretto di registro,

● indiretto con registro.

Questa macchina potrebbe essere il PD32. © 2015

Architettura degli Elaboratori a

Codifica della 2 soluzione 12

. . . 37

MOVL IND+12, R1 ; valore iniziale del puntatore

MOVB #100, R0 ; valore iniziale del contatore

LOOP: JNR AD4, LOOP ; protocollo di input per la …

LOOP1: START AD4 ; … acquisizione …

WAIT: JNR AD4, WAIT ; … del …

INW AD4, (R1) ; … dato

ADDL #2, R1 ; incremento del puntatore

SUBB #1, R0 ; aggiornamento del contatore

JNZ LOOP1 ; iterazione se R0 0

¹

. . . © 2015

Architettura degli Elaboratori

a

3 soluzione 13

Si voglia usare anche l’indirizzamento con registro

indice; 37

- i metodi di indirizzamento disponibili siano:

● immediato,

● assoluto (diretto),

● diretto di registro,

● indiretto con registro,

● con registro indice.

Questa macchina potrebbe essere il PD32. © 2015

Architettura degli Elaboratori a

Codifica della 3 soluzione 14

MOVL #0, R1 ; valore iniziale dell’offset

MOVB #100, R0 ; valore iniziale del contatore 37

LOOP: JNR AD4, LOOP ; protocollo di input per la …

LOOP1: START AD4 ; … acquisizione …

WAIT: JNR AD4, WAIT ; … del …

INW AD4, TAB4(R1) ; … dato

ADDL #2,R1 ; incremento dell’offset

SUBB #1,R0 ; aggiornamento del contatore

JNZ LOOP1 ; iterazione se R0 0

¹

. . .

Specificando gli indirizzi base TAB1, TAB2, … nell’istruzione che

memorizza il dato acquisito, con lo stesso valore in R1 si potrà collocare

il set di 5 campioni in posizioni di pari indice nelle 5 tabelle.

Questo sarà il metodo usato nella soluzione completa. © 2015

Architettura degli Elaboratori

a

4 soluzione 15

Si voglia usare l’indirizzamento con registro indice

indiretto (pre-indexed); 37

- i metodi di indirizzamento disponibili siano:

● immediato,

● assoluto (diretto),

● diretto di registro,

● indiretto con registro,

● con registro indice,

● con registro indice indiretto (pre-indexed).

Questa macchina non è il PD32 (potrebbe essere il

PD132). © 2015

Architettura degli Elaboratori a

Codifica della 4 soluzione 16

. . .

MOVL #12, R1 ; valore nel registro indice 37

MOVB #100, R0 ; valore iniziale del contatore

LOOP: JNR AD4, LOOP ; protocollo di input per la …

LOOP1: START AD4 ; … acquisizione …

WAIT: JNR AD4, WAIT ; … del …

INW AD4, @IND(R1) ; … dato

IND(R1) ; incremento del puntatore in

ADDL #2, ; memoria (PD132!)

; attenzione: così si altera il

; contenuto della tabella IND

SUBB #1, R0 ; aggiornamento del contatore

JNZ LOOP1 ; iterazione se R0 0

¹

. . . © 2015

Architettura degli Elaboratori

a

5 soluzione 17

Si voglia usare il registro indice indiretto nella forma

post-indexed; 37

- i metodi di indirizzamento disponibili siano:

● immediato,

● assoluto (diretto),

● diretto di registro,

● indiretto con registro,

● con registro indice,

● con registro indice indiretto (post-indexed).

Questa macchina non è il PD32 (potrebbe essere il

PD132). © 2015

Architettura degli Elaboratori a

Codifica della 5 soluzione 18

. . .

PT: .DSL 1 ; puntatore (a TAB4) 37

. . .

MOVL #12, R1 ; valore iniziale del …

MOVL IND(R1), PT ; … puntatore

MOVB #100, R0 ; valore iniziale del contatore

MOVL #0, R1 ; valore iniziale del registro indice

LOOP: JNR AD4, LOOP ; protocollo di input per …

LOOP1: START AD4 ; … la acquisizione …

WAIT: JNR AD4, WAIT ; … del …

INW AD4, [@PT](R1) ; … dato

ADDL #2, R1 ; incremento del registro indice

SUBB #1, R0 ; aggiornamento del contatore

0

JNZ LOOP1 ; iterazione se R0 ¹

. . . © 2015

Architettura degli Elaboratori

a

6 soluzione 19

Con l’indirizzamento auto-incrementante si ottiene la

soluzione più efficiente (minor numero di istruzioni!); 37

- i metodi di indirizzamento disponibili siano:

immediato,

● assoluto (diretto),

● diretto di registro,

● indiretto con registro,

● post-incrementante e pre-decrementante

● con registro indice,

Questa macchina è il PD32. © 2015

Architettura degli Elaboratori a

Codifica della 6 soluzione 20

. . . 37

MOVL IND+12, R1 ; valore iniziale del puntatore

MOVB #100, R0 ; valore iniziale del contatore

LOOP: JNR AD4, LOOP ; protocollo di input per la …

LOOP1: START AD4 ; … acquisizione …

WAIT: JNR AD4, WAIT ; … del dato …

INW AD4, (R1)+ ; … + incremento del puntatore

SUBB #1, R0 ; aggiornamento del contatore

0

JNZ LOOP1 ; iterazione se R0 ¹

. . . © 2015

Architettura degli Elaboratori

Soluzioni esaminate - 1 21

Se non è disponibile un indirizzamento tramite registro,

bisogna ricorrere ad una locazione di memoria che svolga 37

le funzioni di puntatore. PT):

Così si è fatto nella prima soluzione (puntatore

STOREW @PT ; memorizzazione del dato

LOAD PT ; incremento

ADD #2 ; …del

STORE PT ; …puntatore

memoria dato

puntatore dato successivo © 2015

Architettura degli Elaboratori

Soluzioni esaminate - 2 22

L’efficienza aumenta se è possibile sfruttare

l’indirizzamento con registro: 37

Così si è fatto nella seconda soluzione (registro R1):

INW AD4, (R1) ; memorizzazione del dato

ADDL #2, R1 ; incremento del puntatore

registro dato

puntatore dato successivo © 2015

Architettura degli Elaboratori

Soluzioni esaminate - 3 23

Se si usa il metodo di indirizzamento con registro indice,

l’indirizzo di ciascun elemento si ottiene come somma di 37

un indirizzo base X e di un offset, fornito da un registro

indice RI. Per individuare elementi diversi si può

RI oppure X.

modificare

L’accesso agli elementi consecutivi di una lista di dati si

ottiene incrementando RI, come fatto nel terzo dei

R1):

metodi presentati (registro indice

INW AD4, TAB4(R1) ; memorizzazione del dato

ADDL #2, R1 ; incremento del puntatore

Con un diverso valore di X (ad es. TAB5 invece di TAB4)

si accede all’elemento di uguale indice in un’altra tabella.

© 2015

Architettura degli Elaboratori

Schematizzazione del terzo metodo 24

37

istruzione

ind. base dato

+ dato successivo

registro

offset © 2015

Architettura degli Elaboratori

Soluzioni esaminate - 3 25

Diversi valori di X, inseriti in istruzioni diverse, 37

consentono di accedere a elementi corrispondenti di

liste diverse, come si è fatto nell’esempio della somma di

due array: 300(R1), R0

MOVW

ADDW 500(R1), R0

MOVW R0, 100(R1)

ADDW #2, R1 © 2015

Architettura degli Elaboratori

Soluzioni esaminate - 4 26

Con l’indirizzamento indiretto e l’uso di un registro

indice nella forma gli elementi della

pre-indexed

struttura di dati sono individuati da un puntatore che si 37

trova all’indirizzo RI + X.

Per scandire gli elementi consecutivi si incrementa tale

puntatore, come si è fatto nel quarto metodo presentato

INW AD4, @IND(R1) ; memorizzazione del dato

ADDL #2, IND(R1) ; incremento del puntatore

; in memoria (PD132!)

istruzione

ind. base puntatore dato

ind. base

registro +

offset dato successivo © 2015

Architettura degli Elaboratori

Soluzioni esaminate - 5 27

Con l’indirizzamento indiretto e l’uso di un registro indice

nella forma l’indirizzo di ciascun elemento è

post-indexed,

fornito dalla somma dell’indirizzo base (puntatore situato 37

X) e dell’offset (contenuto nel registro RI).

all’indirizzo

Gli elementi successivi possono essere individuati

incrementando RI, come si è fatto nel quinto dei metodi

presentati (registro indice R1):

INW AD4, [@PT](R1) ; memorizzazione del dato

ADDL #2, R1 ; incremento del reg. indice

In alternativa, sarebbe stato possibile incrementare il

puntatore base (situato all’indirizzo PT):

INW AD4, [@PT](R1) ; memorizzazione del dato

ADDL #2, PT ; incremento del puntatore

© 2015

Architettura degli Elaboratori

Schematizzazione del quinto metodo 28

istruzione 37

indir. punt. memoria

puntatore dato

+ dato successivo

registro

offset © 2015

Architettura degli Elaboratori

Soluzioni esaminate - 6 29

I metodi di indirizzamento con registro (diretto,

indiretto, auto-incrementante e auto-decrementante) 37

sono, per questo tipo di problemi, i più efficienti.

La possibilità di auto-aggiornamento consente di

risparmiare istruzioni, come appare dal sesto dei metodi

presentati:

INW AD4, (R1)+ ; memorizzazione del dato

; + incremento del puntatore

registro dato

puntatore dato successivo © 2015

Architettura degli Elaboratori

Soluzione completa 30

Si tratta ora di codificare la soluzione completa, che

acquisisce 100 set di 5 campioni simultanei dai 5 37

specifiche di tempo reale:

convertitori, rispettando le

evitare perdita di dati, dopo l’avvio del campionamento

▪per

(fronte di salita del clock) il processore deve acquisire i 5

campioni e ricopiarli in memoria, prima che i valori

contenuti nei Ru vengano sovrascritti dai nuovi campioni

i

prodotti dal successivo fronte di salita del clock:

l’esecuzione di tutte le istruzioni (che acquisiscono i 5 dati,

li mettono in memoria e comandano l’acquisizione dei

successivi 5) deve durare meno del periodo del clock.

garantire la simultaneità dei 5 campioni acquisiti ad

▪per

ogni “tic” del clock, il processore deve inviare il comando

START a tutti 5 i dispositivi, prima del (successivo) fronte

di salita del clock. © 2015

Architettura degli Elaboratori

Soluzione completa: avvio 31

37

© 2015

Architettura degli Elaboratori

Soluzione completa: ciclo iterativo 32

37

© 2015

Architettura degli Elaboratori

Soluzione completa: diagramma temporale 33

= tempo di conversione massimo

t

c MAX = tempo di esecuzione del ciclo V1: • • • JMP V1

t

L 37

= periodo del clock che sincronizza il campionamento

T

Per rispettare le specifiche real-time, deve essere:

t < T - t

L c MAX © 2015

Architettura degli Elaboratori

Esercizio 34

Con riferimento al sistema di acquisizione di 100

set da 5 campioni dai 5 convertitori A/D, 37

supponendo che il tempo di conversione dei 5

▪ t

c

convertitori sia compreso tra 1 e 1.2 e

µs µs,

nell’ipotesi che il tempo di esecuzione delle

▪ istruzioni del PD32 (comprese le operazioni di

fetch) sia di 200 ns se la codifica dell'istruzione

occupa un long word, 300 ns se occupa 2 long

word, e 400 ns se occupa 3 long word,

si calcoli il periodo minimo del clock che

T MIN

garantisce la contemporaneità dei campioni

acquisiti e la non perdita dei dati. © 2015

Architettura degli Elaboratori

Soluzione dell’esercizio 35

; istruzioni del ciclo iterativo e relativi tempi d’esecuzione

V1: JNR AD1, V1 ; 2L 300ns

INW AD1, TAB1(R1) ; 2L 300ns

V2: JNR AD2, V2 ; 2L 300ns 37

INW AD2, TAB2(R1) ; 2L 300ns

V3: JNR AD3, V3 ; 2L 300ns

INW AD3, TAB3(R1) ; 2L 300ns

V4: JNR AD4, V4 ; 2L 300ns

INW AD4, TAB4(R1) ; 2L 300ns

V5: JNR AD5, V5 ; 2L 300ns

INW AD5, TAB5(R1) ; 2L 300ns

ADDL #2, R1 ; 2L 300ns

SUBB #1, R0 ; 2L 300ns

JZ FINE ; 2L 300ns

START AD1 ; 1L 200ns

START AD2 ; 1L 200ns

START AD3 ; 1L 200ns

START AD4 ; 1L 200ns

START AD5 ; 1L 200ns

JMP V1 ; 2L 300ns

;----------------------------------

; totale 5’200ns

t

L © 2015

Architettura degli Elaboratori

Soluzione: considerazioni - 1 36

Prima che sia trascorso un periodo del clock, il processore

deve completare l’acquisizione dei 5 campioni e comandare 37

l’acquisizione dei 5 successivi;

deve, cioè, completare l’esecuzione di tutte le istruzioni

comprese tra V1: … e JMP V1.

Va tenuto inoltre presente il fatto che le istruzioni di

attesa (Vx: JNR ADx, Vx) sono destinate ad essere

eseguite più volte, in attesa che, trascorso il tempo di

conversione, il dato sia pronto.

Per rispettare le specifiche del problema, va considerato

il caso peggiore, che si ha quando il primo dei dispositivi

che vengono esaminati (AD1) sia il più lento (quello che ha

un tempo di conversione pari a = 1200ns).

t

c MAX © 2015

Architettura degli Elaboratori

Soluzione: considerazioni - 2 37

Nelle ipotesi fatte, il primo ciclo di attesa

(V1: JNR AD1, V1) viene eseguito tante volte quante sono

necessarie a far trascorrere i 1200ns . 37

Nel caso peggiore, trascorso questo tempo, deve ancora

iniziare il fetch della istruzione V1: JNR AD1, V1 (la cui

esecuzione trova READY = 1 e consente di uscire dal ciclo di

attesa). Pertanto la durata complessiva di questo ciclo di

attesa è, al più, 1200+300ns.

La durata totale del ciclo V1: … JMP V1 è, nel caso peggiore,

(i 300ns di cui sopra sono già

1200ns + 5200ns = 6400ns

conteggiati nei 5200ns dell’esecuzione del ciclo).

Allo stesso risultato si arriva usando la formula

t < T - t

L c MAX

da cui si ottiene: = 5200ns + 1200ns = 6400ns.

T > t + t

L c MAX

In conclusione il periodo minimo del clock è = 6400ns

T MIN © 2015

Architettura degli Elaboratori Fine

02.e Uso dei modi di indirizzamento

Testo di rif.to:

[Congiu] – 4.4.2 (pg. 159–168) Le Strutture di dati

04.a Vettori (array) e Matrici

Liste LIFO (stack)

Liste FIFO (buffer circolare)

Liste concatenate, alberi

Accesso alle strutture di dati 1

assembly

A livello di linguaggio , c’è la completa

visibilità di come sono organizzate in memoria le 30

strutture di dati con i loro elementi.

Esaminiamo ora come si definiscono le più

comuni strutture dati e come si accede ai loro

elementi:

• Vettori

• Matrici

• LIFO (stack)

Liste di tipo

• FIFO (buffer circolari)

Liste di tipo

• Liste concatenate

• Alberi © 2016

Architettura degli Elaboratori

Vettori (array) 2

In linguaggio assembly, la definizione di un array si

effettua specificandone le seguenti informazioni: 30

● l’indirizzo iniziale in memoria V,

● il numero degli elementi N,

● la lunghezza L di ciascun elemento (espressa in byte).

Organizzazione in

memoria di un vettore

di N elementi © 2016

Architettura degli Elaboratori

Definizione di un array 3

La definizione dell’array in figura può essere 30

fatta con le seguenti direttive:

.BSS

V: .DSB N*L

.BSS (dati non inizializzati)

• una direttiva label (V:), che

• definisce l’indirizzo iniziale

dell’area di memoria;

una direttiva (.DSB), che ne

• definisce l’estensione (in byte) © 2016

Architettura degli Elaboratori

Accesso agli elementi di un array 4

Per accedere agli elementi di un vettore si può usare un

metodo di indirizzamento a due componenti (ad es. con

registro indice): una componente, che rimane fissa, è 30

V; l’altra, destinata a

costituita dall’indirizzo iniziale

variare, fornisce l’offset dell’elemento rispetto a V.

L’indirizzo dell’elemento V[i] (ind V[i]) è V + offset.

L’accesso all’elemento di indice i richiede di trasformare

l’indice nel corrispondente offset i*L:

l’indice i parte da zero

ind V[i]= V + i*L (se )

- il calcolo dell’offset richiede una moltiplicazione

se l’indice i parte da uno

ind V[i]= V + (i-1)*L ( )

- il calcolo dell’offset richiede un’operazione in più

È più conveniente che l’indice i parta da zero. © 2016

Architettura degli Elaboratori

Accesso agli elementi di un array 5

Se L = 1 l’offset è uguale all’indice i

Se L = potenza intera di 2, allora il calcolo dell’offset 30

può essere ottenuto con una semplice operazione di

(i*L)

scorrimento aritmetico verso sinistra.

Es: sia L=4 e R1 contenga l’indice i:

; i*4 (indice®offset)

ASLL 2, R1 ; accesso all’elemento

V(R1)

MOVL R0,

Negli altri casi per ottenere l’offset è necessario

calcolare il prodotto (i*L): in termini di tempo di

esecuzione una moltiplicazione è più gravosa di una

somma o di uno shift. © 2016

Architettura degli Elaboratori

Matrici 6

matrice possono essere

Gli elementi di una

collocati in memoria ordinati per riga oppure per 30

colonna.

Organizzazione per righe

di una matrice con R righe e C colonne © 2016

Architettura degli Elaboratori

Definizione di una matrice 7

La definizione di una matrice richiede di

specificare le seguenti informazioni: 30

● L’indirizzo iniziale M

● Il numero di righe R

● Il numero di colonne C

● La lunghezza L di ciascun elemento.

La definizione della matrice in figura può

essere fatta con le seguenti direttive:

.BSS

M: .DSB R*C*L © 2016

Architettura degli Elaboratori

Accesso agli elementi di una matrice - 1 8

Per individuare un elemento si usano

due indici: uno di riga (i) e uno di 30

colonna (j).

L’indirizzo dell’elemento M[i,j] è dato da:

ind M[i,j] = M + (i*C+j)*L

Anche in questo caso conviene usare un

metodo di indirizzamento a due

componenti in cui l’indirizzo base è

costituito da M e l’offset deve essere

calcolato (ad es. in un registro indice)

valutando l’espressione (i*C+j)*L © 2016

Architettura degli Elaboratori

Accesso agli elementi di una matrice - 2 9

Esempio: 30

elementi della matrice: word (L=2)

● si voglia eseguire R0

● ®M[i,j]

W

i sia contenuto in R1 e j in R2.

● ;

UMUL #C, R1 i*C

; (i*C+j)

ADDL R2, R1 ; (i*C+j)*2 (offset)

ASLL 1, R1

MOVW R0, M(R1)

per ottenere l’offset è comunque

necessario calcolare il prodotto i*C.

© 2016

Architettura degli Elaboratori

Matrice con array ausiliario di puntatori 10

Utilizzando un array ausiliario di puntatori, come in

i*C e l’accesso alla

figura, si evita il calcolo del prodotto

matrice si riconduce a 2 accessi ad array. 30

a

inizio 2 riga

a

inizio ult riga Accesso alle righe di una matrice

tramite l’array ausiliario P:

P[i] punta all’inizio della riga di

indice i. © 2016

Architettura degli Elaboratori

Accesso con array ausiliario di puntatori 11

Definizione della matrice M e dell’array ausiliario P:

.BSS ; area dati non inizializzati 30

M: .DSB R*C*L

.DATA ; area dati inizializzati

P: .DCL M, M+C*L, M+2*C*L, …, M+(R-1)*C*L

Con L=2, i in R1 e j in R2, il trasferimento R0 si

®M[i,j]

W

può ottenere così: i*4 (gli elementi di P sono ptr)

ASLL 2, R1 ; P[i]®R1 (inizio di riga i-esima)

MOVL P(R1), R1 ; j*2 (offset in riga i-esima)

ASLL 1, R2 ; P[i]+(j*2) (indirizzo di M[i,j])

ADDL R2, R1 ;

MOVW R0, (R1) ; © 2016

Architettura degli Elaboratori

Accesso con array ausiliario di offset - 1 12

Al posto dell’array di puntatori P, è meglio usare un

O che contenga gli offset di ciascuna

array ausiliario 30

M:

riga rispetto all’indirizzo iniziale

.BSS

M: .DSB R*C*L

.DATA

O: .DCW 0, C*L, 2*C*L, …, (R-1)*C*L

Mentre i puntatori dell’array P sono da 4 byte, gli offset

di O possono spesso essere da 2 o da 1 byte;

Un unico array O di offset può essere utilizzato per

tutte le matrici dello stesso tipo (stesso numero di righe

e di colonne e stessa lunghezza degli elementi). © 2016

Architettura degli Elaboratori

Accesso con array ausiliario di offset - 2 13

Usando l’array O di offset, con L=2, i in R1 e j in R2, il trasferimento

si può ottenere così:

R0 M[i,j]

®

W i*2 (offset di O[i] in O)

ASLL 1, R1 ; 30

O[i]®R1 (offset della riga i-esima)

MOVW O(R1), R1 ; j*2 (offset nella riga i-esima)

ASLL 1, R2 ; O[i]+(j*2) (offset di M[i,j])

ADDL R2, R1 ; di M[i,j]]

R0

MOVW R0, M(R1) ; ®W[M+offset

W

Disponendo in un indirizzamento con reg. base e reg. indice:

i*2 (offset di O[i] in O)

ASLL 1, R1 ; O[i]®R1 (offset della riga i-esima)

MOVW O(R1), R1 ; j*2 (offset nella riga i-esima)

ASLL 1, R2 ; R0

MOVW R0, M(R1, R2) ; ®W[M+R1+R2]

W

Il metodo può essere esteso al caso di una matrice Z di N dimensioni

(con N indici x , x , …, x ), usando N-1 array ausiliari (uno per ciascuno

1 2 N

dei primi N-1 indici): gli elementi dell’array ausiliario associato

all’indice x (con K=1..N-1) forniscono gli offset delle sottomatrici di

K

N-K dimensioni (con indici x , x , ..., x ).

K+1 K+2 N © 2016

Architettura degli Elaboratori

Liste LIFO (stack) 14

Definizionedi un’ area di

memoria di 4KB riservata ad

uno stack: 30

STL = 4096 Stack

.DSB STL Pointer

ST: .DSB 1 Indirizzi

Inizializzazione dello stack crescenti

R7:

pointer Organizzazione di uno stack

MOVL #ST, R7

Operazione push di un

elemento lungo un word (R0 ):

W

MOVW R0, -(R7)

Operazione pop:

MOVW (R7)+, R1 © 2016

Architettura degli Elaboratori

Liste FIFO (coda) - 1 15

Una lista FIFO è in genere costituita da una struttura

buffer circolare:

di dati che prende il nome di 30

POUT OUT

PIN IN

Organizzazione di un buffer circolare © 2016

Architettura degli Elaboratori

Liste FIFO (coda) - 2 16

Nel PD32 le direttive per definire un buffer circolare

sono indicate nel seguente esempio: 30

L = 1 ; lunghezza di un elemento

QL = 100 ; numero di elementi

.BSS

QUE: DSB (QL-1)*L

LAST: DSB L

.DATA

PIN: .DCL QUE ; puntatore inserzione

POUT: .DCL QUE ; puntatore estrazione

Agli indirizzi PIN e POUT, sono mantenuti i

puntatori usati per l’inserzione (IN) e per ~ ~

l’estrazione (OUT). PIN IN

Inizialmente (coda vuota) essi puntano OUT

entrambi al primo elemento della lista. POUT © 2016

Architettura degli Elaboratori

Inserzione di un elemento nel buffer circolare 17

Inserzione di un elemento (il byte R0 )

B

; puntatore per l’inserzione

MOVL PIN, R1 30

; inserzione

MOVB R0, (R1)+ ; aggiornamento del puntatore

MOVL R1, PIN bit

; R1-(LAST+L)® di condizione

CMPL #LAST+L, R1 ; se C=0, R1 < LAST+L (R1 LAST)

JNC OK ≤

; (nella sottrazione, C=0 se

; c’è un “prestito”)

; altrimenti R1 LAST+L

MOVL #QUE, PIN ≥

; (R1 > LAST)

OK: …… © 2016

Architettura degli Elaboratori

Estrazione di un elemento dal buffer circolare 18

Estrazione di un elemento (nel byte R0 )

B

; puntatore per l’estrazione

MOVL POUT, R1 30

; estrazione

MOVB (R1)+, R0 ; aggiornamento del puntatore

MOVL R1, POUT bit

; R1-(LAST+L)® di condizione

CMPL #LAST+L, R1 ; se C=0, R1 < LAST+L (R1 LAST)

JNC OK1 ≤

; (nella sottrazione, C=0 se

; c’è un “prestito”)

; altrimenti R1 LAST+L

MOVL #QUE, POUT ≥

; (R1 > LAST)

OK1: …… © 2016

Architettura degli Elaboratori

Buffer circolare: offset anziché puntatori - 1 19

Il ripristino del valore iniziale dei puntatori,

LAST, si ottiene in modo

quando questi superano 30

più agile se l’estensione del buffer è pari ad una

q

potenza intera di 2 (2 ). puntatori, si possono

In tal caso, al posto dei

offset

usare gli relativi all’inizio del buffer,

q

2 .

incrementati modulo

Quest’ultima operazione può essere effettuata

q bit meno significativi del

considerando solo i

valore incrementato, che si possono isolare

q

AND con il valore 2 - 1.

eseguendo un © 2016

Architettura degli Elaboratori

Buffer circolare: offset anziché puntatori - 2 20

Esempio: 30

Definizione di un buffer circolare, avente una

8 =256 byte:

estensione di 2

.BSS

BQUE: .DSB 256

.DATA offset

XIN: .DCB 0 ; iniziale di inserzione

offset

XOUT: .DCB 0 ; iniziale di estrazione

© 2016

Architettura degli Elaboratori

Buffer circolare: offset anziché puntatori - 3 21

Inserzione di un elemento (il byte R0 )

B 30

offset

MOVB XIN, R1 ; per l’inserzione

ANDL #$FF, R1 ; azzera i 3 MSBy

MOVB R0, BQUE(R1) ; inserzione offset

ADDL #1, R1 ; incremento dell’ offset

MOVB R1, XIN ; aggiornamento dell’

; (estrae da R1 solo il LSBy)

© 2016

Architettura degli Elaboratori

Buffer circolare: offset anziché puntatori - 4 22

Estrazione di un elemento (nel byte R0 )

B 30

offset

MOVB XOUT, R1 ; per l’estrazione

ANDL #$FF, R1 ; azzera i 3 MSBy

MOVB BQUE(R1), R0 ; estrazione offset

ADDL #1, R1 ; incremento dell’ offset

MOVB R1, XOUT ; aggiornamento dell’

; (estrae da R1 solo il LSBy)

© 2016

Architettura degli Elaboratori

Buffer circolare pieno/vuoto 23

Le operazioni vanno precedute dalla verifica che il buffer

non sia già pieno o, rispettivamente, vuoto. 30

Quando il buffer è pieno si ha XIN = XOUT

(XIN, fatto il “giro” raggiunge XOUT dopo aver occupato l’ultimo

elemento libero del buffer).

Ma …

Anche quando il buffer è vuoto si ha XIN = XOUT

(XOUT, fatto il “giro” raggiunge XIN dopo aver estratto l’ultimo

elemento presente nel buffer).

La condizione XIN = XOUT non consente di distinguere

i due casi.

Conviene considerare pieno il buffer circolare

Þ quando c’è un solo elemento libero. © 2016

Architettura degli Elaboratori

Buffer circolare: verifica se pieno 24

Inserzione di un elemento (il byte R0 )

B 30

offset

MOVB XIN, R1 ; per l’inserzione

ANDL #$FF, R1 ; azzera i 3 MSBy

MOVB R0, BQUE(R1) ; elemento inserito comunque

offset

ADDL #1, R1 ; incremento dell’

CMPB XOUT, R1 ; se era l’ultimo libero …

JZ PIENA ; … allora la coda è piena:

; XIN non viene aggiornato!

MOVB R1, XIN ; aggiornamento di XIN

. . . ; inserzione avvenuta

PIENA: . . . ; inserzione non avvenuta © 2016

Architettura degli Elaboratori

Buffer circolare: verifica se vuoto 25

Estrazione di un elemento (nel byte R0 )

B 30

offset

MOVB XOUT, R1 ; per l’estrazione

ANDL #$FF, R1 ; azzera i 3 MSBy

CMPB XIN, R1 ; XIN=XOUT?

JZ VUOTA ; si: la coda è vuota,

; non si estrae

MOVB BQUE(R1), R0 ; estrazione offset

ADDL #1, R1 ; incremento dell’

MOVB R1, XOUT ; aggiornamento di XOUT

. . . ; estrazione avvenuta

VUOTA: . . . ; estrazione non avvenuta © 2016

Architettura degli Elaboratori

Liste concatenate 26

30

• Ad ogni elemento di una lista concatenata (linked list) è

puntatore che individua l’elemento successivo.

associato un

• Gli elementi contengono un campo puntatore (4 byte) e

possono trovarsi ovunque in memoria.

Nel PD32 le direttive con cui definire una lista

- concatenata (inizialmente vuota) sono:

NIL = -1

HEAD: .DCL NIL

Se R1 punta a un elemento, con l’istruzione:

- MOVL (R1), R1

R1 punta all’elemento successivo (e si percorre la lista).

© 2016

Architettura degli Elaboratori

Liste concatenate: inserzione 27

Esempio:

inserzione, a fine lista, di un elemento (puntato da R0) 30

; puntatore iniziale

MOVL #HEAD, R1 ; campo indirizzo

CERCA: MOVL (R1), R2 ; è l’ultimo elemento?

CMPL #NIL, R2 ; si, è l’ultimo

JZ ULTIMO ; elemento successivo

MOVL R2, R1

JMP CERCA ; aggancio

ULTIMO: MOVL R0, (R1) ; l’elemento inserito è

MOVL #NIL, (R0) ; ora l’ultimo © 2016

Architettura degli Elaboratori

Liste concatenate: estrazione 28

Esempio:

estrazione del primo elemento (puntatore in R0) 30

MOVL #HEAD, R1 ; puntatore iniziale

MOVL (R1), R0 ; puntatore all’elemento

; da estrarre

CMPL #NIL, R0 ; lista vuota?

JZ VUOTA ; si, non estrae

MOVL (R0), (R1) ; estrazione: il campo

; puntatore dell’elemento

; estratto viene ricopiato

; in L[HEAD]

VUOTA: …… …… © 2016

Architettura degli Elaboratori

Liste concatenate: esercizi proposti 29

Gli esempi visti (inserzione alla fine, estrazione

dalla testa) corrispondono ad usare la lista con 30

modalità FIFO (coda);

Si propongono altri esercizi:

1. inserzione e estrazione usando la lista con modalità

LIFO (entrambe dalla testa);

2. inserzione di un dato in una lista ordinata (va prima

individuato il punto in cui effettuare l’inserzione);

3. ricerca di un dato in una lista ordinata;

4. estrazione di un elemento da una lista ordinata, se

.

presente © 2016

Architettura degli Elaboratori

Alberi 30

Ciascun elemento della struttura comprende una lista di

puntatori ad altri elementi della struttura. 30

Gli elementi terminali hanno NIL nei campi puntatore.

Nel caso dell’albero binario: © 2016

Architettura degli Elaboratori Fine

04.a Le Strutture di dati

Introduzione ad ARM

e al processore S3C2440

03.a C. Fantozzi, A. Gardich

(revisione di S. Congiu, M.Moro)

Che cosa è ARM? 1

ARM = Advanced RISC Machine 46

ARM Ltd non produce microprocessori:

progetta e vende proprietà intellettuale

ARM è una architettura:

insieme dei registri e delle istruzioni disponibili

▪ modi d’indirizzamento

▪ gestione delle interruzioni

Esistono molte versioni dell’architettura,

e molti processori per versione © 2016

Architettura degli Elaboratori

ARM nella vita quotidiana: esempi 2

SAMSUNG Galaxy S6 [Cortex A53+Cortex A57]

iPHONE 6 [Cortex A72 (A8)+Cortex M3 (M8)] 46

Nintendo 3DS (ARM11 quadcore)

Molte calcolatrici e palmari ... © 2016

Architettura degli Elaboratori

Architettura ARM: versioni 3

Sono state definite (da 1 a 8)

8 versioni (architetture)

del set di istruzioni ARM. 46

Per ogni versione esistono identificate da

varianti,

lettere:

T (Thumb: istruzioni da 16 bit)

● M (Multiply: con prodotto da 64 bit)

● E (Enhanced: con istruzioni DSP per applicazioni multimediali

Le più diffuse nei sistemi embedded portatili

(smartphones, Personal Digital Assistants, …) sono le

architetture (versioni) 4 e 5 e, più recentemente, per

applicazioni con esigenze di alte prestazioni, le versioni 7

e 8 (famiglia CORTEX). © 2016

Architettura degli Elaboratori

Architettura ARM: famiglie 4

Diversi fornitori hanno prodotto diverse famiglie di

processori ARM, basate su diverse versioni del core ARM. 46

Le famiglie di processori ARM attualmente più diffuse sono:

FAMIGLIA VERSIONE ARM

ARM7 ARMv3

ARM9 ARMv4T

ARM9E ARMv5TE

ARM10E ARMv5TE

XScale ARMv5TE

ARM11 ARMv6

Cortex-A (32 bit) ARMv7-x (anche ARMv6-M)

Cortex-A (64 bit) ARMv8-A © 2016

Architettura degli Elaboratori

La famiglia Cortex 5

• Presentata nel 2005, si caratterizza per essere costituita da un

insieme di unità funzionali collegabili tra loro

• Uno specifico processore ne può realizzare un sottoinsieme 46

serie A (application) è quella più completa (computer,

smartphone, ecc.)

serie R (realtime), floating point opzionale, cache configurabile,

MMU più semplice

serie M (microcontroller) è quella più semplice, cache assente o

limitata, MMU opzionale

• Le diverse configurazioni possono essere a singolo core o multicore

• Alcune caratteristiche specifiche delle architetture v7 e V8

• unità NEON per operazioni SIMD su 64 o 128 bit

• unità floating point con più registri e nuove operazioni

• set di istruzioni Thumb per accelerare l’esecuzione di macchine

virtuali (es. JVM)

• modalità di esecuzione sicura (TrustZone) © 2016

Architettura degli Elaboratori

Cortex–M7 (ARMv7E-M Microcontroller) 6

46

© 2016

Architettura degli Elaboratori

Cortex-A72 (ARMv8-A Application) 7

46

© 2016

Architettura degli Elaboratori

Samsung S3C24xx Application Processors 8

Applicazioni Obiettivi di progetto

Mobile Computing ● Insieme completo di 46

periferiche on-chip

● Portable Network Devices

● Portable media players ● Elevate prestazioni

● Edutainment toys ● Basso consumo

● E-book readers ● Rapporto

Mobile Communication prezzo/prestazioni

● Smartphones © 2016

Architettura degli Elaboratori

S3C2440: specifiche tecniche 9

14x14 mm 289-pin FBGA

Processore RISC a 32 bit

Architettura ARMv4T (Fine Ball Grid Array)

●Famiglia ARM9T; 46

Processo produttivo: 130 nm

●Core ARM 920T; thumb i.s. Frequenza: 533 MHz max

●Memory Management Unit Bus memoria: 100 MHz max

●Cache (instruction & data)

Nessun HW floating point Tensione di alimentazione 1.2V

Funzionalità integrate: Consumo: 0,368W @ 400 MHz

●ADC a 10 bit, 8 canali;

●3 porte seriali;

●USB host & device;

●controller LCD, touch screen;

●Interfacce per sensori CMOS,

schede di memoria, audio, ecc.

Technical Reference Manual del processore ARM 920

:

http://infocenter.arm.com/help/topic/com.arm.doc.ddi0151c/ARM920T_TRM1_S.pdf

© 2016

Architettura degli Elaboratori

S3C2440: schema a blocchi 10

46

© 2016

Architettura degli Elaboratori

ARMv4: caratteristiche 11

L’architettura ARMv4 è a 32 bit 46

● word=32 bit

(in memoria allineati ad indirizzi multipli di 4)

● halfword=16 bit

(in memoria allineati ad indirizzi multipli di 2)

● byte =8 bit

(singolarmente indirizzabili in memoria)

32

2 byte di memoria indirizzabili (4GB), ma

S3C2440 supporta max 1 GB (8 banchi da 128 MB)

© 2016

Architettura degli Elaboratori

ARMv4: caratteristiche RISC 12

L’architettura ARMv4 è di tipo RISC 46

Numero elevato di registri (37 in tutto)

● Istruzioni con lunghezza fissa di 32 bit

● Le parole di estensione non esistono,

● load

Architettura load/store: ad esclusione di

● store

e , tutte le istruzioni operano su registri

Modi di indirizzamento semplici: tutti gli

● indirizzi di memoria nelle istruzioni load/store

sono specificati da informazioni contenute in

registri o nei campi dell’istruzione © 2016

Architettura degli Elaboratori

ARMv4: altre caratteristiche 13

• Controllo sia dell’ALU sia dello shifter, con 46

tutte le istruzioni di elaborazione-dati

• Modalità di indirizzamento auto-incrementanti

e auto-decrementanti (efficienza nei loop)

• Esecuzione condizionata specificabile in tutte

le istruzioni

• Istruzioni di load e store multipli (più registri)

• Shift di n posizioni in un solo ciclo di clock

• Istruzioni a 3 operandi © 2016

Architettura degli Elaboratori

Modi operativi 14

User (USR): modo utente

FIQ (FIQ): gestione veloce interruzioni 46

IRQ (IRQ): gestione interruzioni

Supervisor (SVC): modo protetto

Abort (ABT): per gestione memoria

Undefined (UND): emulaz. coprocessori

System (SYS): usa risorse di USR

senza limitazioni d’accesso © 2016

Architettura degli Elaboratori

I registri: panoramica 15

46

© 2016

Architettura degli Elaboratori

I registri 16

registri di uso generale

R0-R13: 46

stack pointer (R13)

SP: link register (R14)

LR:

Memorizza l’indirizzo di ritorno da subroutine

program counter (R15)

PC:

Punta all’istruzione da eseguire

Current Program Status Register

CPSR:

Contiene i bit di stato

Saved Program Status Register

SPSR:

Copia di CPSR prima del cambio di modo © 2016

Architettura degli Elaboratori

CPSR: bit utili 17

• Bit 0–4 (M): modo operativo (7 attualmente previsti)

• Bit 7 (I): interruzioni on/off (0/1)

• Bit 28 (V): indica errore di overflow 46

(aritmetica con segno in complemento a 2)

carry

indica il o riporto

• Bit 29 (C): (overflow nell’aritmetica senza segno)

• Bit 30 (Z): indica un risultato zero

indica un risultato negativo

• Bit 31 (N): (aritmetica con segno in complemento a 2)

Altri bit:

• Bit 5 (T): Thumb instruction set off/on (0/1)

• Bit 6 (F): fast IRQ on/off (0/1)

• Bit 7 (I): IRQ on/off (0/1)

Riservati © 2016

Architettura degli Elaboratori

Big o Little Endian? 18

S3C2440 supporta tutte e 2 le modalità 46

Il comportamento predefinito è

secondo specifiche ARM

little endian, © 2016

Architettura degli Elaboratori

Operazioni di I/O 19

L’I/O è di tipo memory mapped:

i registri delle periferiche si trovano in

● 46

locazioni di memoria predefinite

2 tipi di interruzioni:

● Normale

(vengono salvati meno registri)

● Fast

Hardware delle periferiche con accesso diretto

alla memoria (DMA) © 2016

Architettura degli Elaboratori

Classificazione delle istruzioni 20

Accesso alla memoria 46

● Load / store tra memoria e registri

Elaborazione di dati (data processing)

● Operazioni di movimento tra registri

● Operazioni aritmetico-logiche

● Operazioni di confronto

Controllo di flusso

● Branch (=“salto”) con o senza condizione © 2016

Architettura degli Elaboratori

Le istruzioni 21

ARMv4 prevede:

- istruzioni di elaborazione dati a 3 operandi: 46

● uno (registro) per il risultato, due per gli operandi:

SUB R2, R0, R1 @ R2=R0-R1

SUB R2, R0, R1, LSL #4 @ R2=R0-R1*16

- altre istruzioni a 2 operandi:

● uno per l’op. destinazione, uno per l’op. sorgente:

MOV R2, R2, ASR #2 @ R2=R2/4

1 operando:

- altre istruzioni a

● ad es. le istruzioni di branch:

B LAB2 © 2016

Architettura degli Elaboratori

Modifica dei bit di stato 22

Per default le istruzioni 46

non modificano i bit di stato N,Z,C,V

Per modificare i bit di stato si aggiunge il

al simbolo mnemonico dell’istruzione:

suffisso S

ADD R2, R0, R1 @ non modifica NZCV

ADDS R2, R0, R1 @ modifica NZCV

Non vale per le istruzioni di confronto! © 2016

Architettura degli Elaboratori

Istruzioni con condizione - 1 23

Aggiungendo specifici suffissi di condizione, 46

l’istruzione viene eseguita solo se i bit di

condizione soddisfano quanto specificato

Esempi:

MOVEQ R0, #0 poni R0=0 solo se Z=1

R0, #0 esegui se Z=0

MOVNE

MOVGT R0, #0 esegui se Z=0 e N=V

R0, #0 esegui se Z=1 o N≠V

MOVLE

MOVAL R0, #0 esegui sempre © 2016

Architettura degli Elaboratori

Istruzioni con condizione - 2 24

Permettono di velocizzare il codice

● risparmiando salti condizionati 46

● mantenendo pieni i pipeline

CMP r0, #10

if (a > 10) return 0; MOVGT r0, #0

else return 1 MOVLE r0, #1

Nessun branch misprediction! © 2016

Architettura degli Elaboratori

Lista delle condizioni 25

Flag di Opcode

Estensione Significato

mnemonica condizione [31:28]

EQ Uguali Z=1 0000 46

NE Non uguali Z=0 0001

CS/HS Carry Attivato / Senza segno maggiore o uguale C=1 0010

CC/LO Carry Disattivato / Senza segno minore C=0 0011

MI Negativo N=1 0100

PL Positivo o Zero N=0 0101

VS Overflow V=1 0110

VC Non Overflow V=0 0111

HI Senza segno maggiore C=1 e Z=0 1000

LS Senza segno minore o uguale C=0 o Z=1 1001

GE Con segno maggiore o uguale N=V 1010

LT Con segno minore N!=V 1011

GT Con segno maggiore Z=0 e N=V 1100

LE Con segno minore o uguale Z=1 o N!=V 1101

AL Sempre (è il default) - 1110

NV Mai - 1111 © 2016

Architettura degli Elaboratori

I modi di indirizzamento 26

Ogni categoria di istruzioni ha i propri: ci sono

4 classi di modi di indirizzamento. 46

RISC:

● niente indirizzamento assoluto (non usa

puntatori in memoria, ma solo nei registri)

● indirizzamento in memoria (indiretto con

registro) solo per le istruzioni LDR (load) e

STR (store) © 2016

Architettura degli Elaboratori

Classi di indirizzamento 27

Modo 1: per istruzioni di elaborazione dati

● ADC, ADD, AND, BIC, CMN, CMP, EOR, MOV, 46

MVN, ORR, RSB, RSC, SBC, SUB, TEQ, TST

Modo 2: per Load&Store di word o unsigned byte

● LDR, LDRB, STR, STRB

Modo 3: per L&S di halfword o signed byte

● LDRH, LDRSB, LDRSH, STRH

Modo 4: per L&S di registri multipli

● LDMxx, STMxx © 2016

Architettura degli Elaboratori

Istruzioni di elaborazione dati 28

3 indirizzi: 46

opcode cond shifter_operand

< >{< >}{S} <Rd>, <Rn>, < >

<cond>

● : stabilisce l’esecuzione condizionata

● S: stabilisce se modifica i bit di condizione

● <Rd>: destinazione

● <Rn>: primo operando

shifter_operand

● < >: secondo operando

addges R4, R3, R2

esempio: @ R4 R3+R2

¬ © 2016

Architettura degli Elaboratori

Modo 1 (indirizz. per elaboraz. dati) 29

sintassi:

<istruzione3op> Rd, Rn, <shifter_operand> 46

<istruzione2op> Rd, <shifter_operand>

può essere:

<shifter_operand>

un valore immediato

● #<valore>

un registro

● Rm

un registro, dopo scorrimento specificato con:

● - un valore immediato Rm, <sop> #<shift_imm>

- un registro Rm, <sop> Rs

gli operatori disponibili sono:

● <sop>

ASR, LSL, LSR, ROR, RRX © 2016

Architettura degli Elaboratori

shifter_operand

< >: indirizzamento immediato 30

Il campo dell’istruzione contiene il valore su cui

operare 46

sintassi: #<immediato>

: add R3, R3, #1

esempio @ R3 R3+1

¬

12 bit a disposizione per l’operando immediato,

con la seguente struttura:

▪ 8 bit (bit c) definiscono un valore c (0 c 255);

£ £

▪ 4 bit (bit r) specificano una rotazione verso destra

di 2r posizioni © 2016

Architettura degli Elaboratori

shifter_operand

< >: indirizzamento immediato 31

31 28 24 21 19 16 15 12 11 8 7 0

cond 0 0 1 opcode S Rn Rd rotate immed_8 46

0x00 c 0xFF

£ £

r 15

0 r c

£ £

2r 30

0 £ £

immediato

#< >=c 2r

>> rot

immediato valido: #0x104 (c=0x41, r=15)

non valido: #0x102

immediato © 2016

Architettura degli Elaboratori

shifter_operand

< >: indirizzamento di registro 32

Il valore su cui operare è contenuto in un registro Rm

Tale valore può essere shiftato di una quantità: 46

specificata in modo immediato (0..31: 5 bit)

● specificata da un altro registro (Rs):

● Rm, LSR #shift_imm Rm, LSR Rs

oppure

Rm, ASR #shift_imm Rm, ASR Rs

oppure

Rm, LSL #shift_imm Rm, LSL Rs

oppure

Rm, ROR #shift_imm Rm, ROR Rs

oppure Rm, RRX

: add R3, R1, R2, LSL #2

esempi @ R3 R1+R2*4

¬

R2, ASR R5

add R3, R1, R5

@ R3 R1+R2/2

¬ © 2016

Architettura degli Elaboratori

shifter_operand

< >: indirizzamento di registro 33

31 28 24 21 19 16 15 12 11 7 5 3 0

cond 0 0 0 opcode S Rn Rd shift_imm sop 0 Rm 46

codifica di Rm, <sop> #shift_imm

31 28 24 21 19 16 15 12 11 7 5 3 0

cond 0 0 0 opcode S Rn Rd Rs 0 sop 1 Rm

codifica di Rm, <sop> Rs

<sop>: 00 LSL

01 LSR

10 ASR

11 ROR (RRX = ROR #0) © 2016

Architettura degli Elaboratori

Modo 1: esempi 34

mov R0, #0 @ R0 0

¬ R3+1

add R3, R3, #1 @ R3 ¬ 46

(R7–1000)

cmp R7, #1000 @ cc ¬

bic R9, R8, #0xff00 @ R9 R8 and not 0xff00

¬ R0

mov R2, R0 @ R2 ¬

add R4, R3, R2 @ R4 R3+R2

¬ R0*4

mov R2, R0, LSL #2 @ R2 ¬ R5+R5*8 = R5*9

add R9, R5, R5, LSL #3 @ R9 ¬ R5–R5/8

sub R9, R5, R5, ASR #3 @ R9 ¬ R5/8–R5

rsb R9, R5, R5, ASR #3 @ R9 ¬

mov R5, R3, RRX @ R5 R3 ruotato esteso

¬

@ a destra di una posiz.

R4 ruotato a destra

mov R7, R4, ROR R3 @ R7 ¬

@ di R3 posizioni © 2016

Architettura degli Elaboratori

Modo 2 (per Word o unsigned Byte) 35

sintassi:

LDR|STR{B} Rd, <addressing_mode2> 46

è un indirizzamento di registro

<addressing_mode2>

con un eventuale:

offset immediato

● offset da registro

● offset da registro scalato

● pre-incremento immediato

● pre-incremento da registro

● pre-incremento da registro scalato

● post-incremento immediato

● post-incremento da registro

● post-incremento da registro scalato

● © 2016

Architettura degli Elaboratori

Modo 2: nessun offset 36

Corrisponde a quello che nel PD32 è

l’indirizzamento indiretto con registro. 46

Il valore dell’operando è puntato da un registro

contiene l’indirizzo

(cioè Rn dell’operando)

Rn sintassi: [Rn]

esempio: ldr R1, [R0] @ R1 M [R0]

¬ 32 © 2016

Architettura degli Elaboratori

Modo 2: offset 37

Offset immediato

● [Rn, #±<offset_12>] 46

@ Rd M[Rn ± <offset_12>]

«

Offset da registro

● [Rn, ±Rm]

@ Rd M[Rn ± Rm]

«

Offset da registro scalato

● [Rn, ±Rm, <sop> #<shift_imm>]

@ Rd M[Rn ± (Rm <sop> # <shift_imm>)]

« © 2016

Architettura degli Elaboratori

Modo 2: pre-incremento 38

Pre-incremento immediato

● [Rn, #±<offset_12>]! 46

@ Rn Rn ± <offset_12>

¬

@ Rd M[Rn]

«

Pre-incremento da registro

● [Rn, ±Rm]!

@ Rn Rn ± Rm

¬

@ Rd M[Rn]

«

Pre-incremento da registro scalato

● [Rn, ±Rm, <sop> #<shift_imm>]!

@ Rn Rn ± (Rm <sop> # <shift_imm>)

¬

@ Rd M[Rn]

« © 2016

Architettura degli Elaboratori

Modo 2: post-incremento 39

Post-incremento immediato

● [Rn], #±<offset_12> 46

@ Rd M[Rn]

«

@ Rn Rn ± <offset_12>

¬

Post-incremento da registro

● [Rn], ±Rm

@ Rd M[Rn]

«

@ Rn Rn ± Rm

¬

Post-incremento da registro scalato

● [Rn], ±Rm, <sop> #<shift_imm>

@ Rd M[Rn]

«

@ Rn Rn ± (Rm <sop> # <shift_imm>)

¬ © 2016

Architettura degli Elaboratori

Pre/post-increm. con registro scalato 40

L’offset contenuto nel registro può essere

Rm

fatto scorrere di un numero di passi specificato 46

con valore immediato da 5 bit (da 0 a 31 passi)

sintassi:

Pre-incremento Post-incremento

[Rn, LSL #num]! [Rn], ±Rm, LSL #num

±Rm, [Rn], ±Rm, LSR #num

[Rn, ±Rm, LSR #num]! [Rn], ±Rm, ASR #num

[Rn, ±Rm, ASR #num]! [Rn], ±Rm, ROR #num

[Rn, ±Rm, ROR #num]! [Rn], ±Rm, RRX

[Rn, ±Rm, RRX]!

esempio:

[R0], -R2, ASR #2

ldr R1, @ R1¬M [R0]; R0¬R0-(R2/4)

32 © 2016

Architettura degli Elaboratori

Indirizzamento auto-relativo 41

Si ottiene usando il registro R15 (PC)

nell’indirizzamento indiretto con registro: 46

●esempi:

[R15, -#8]

ldr R1, @ R1 M [R15-8]

¬ 32

ldr PC, [PC, R0, LSL #2] @ PC M [PC+R0*4]

¬ 32

Il valore di R15 usato è PC_istruz.+8 o +12 a

causa del prefetching

• Lo shift è specificato tramite un valore immediato:

l valore di R15 usato è PC_istruz.+8

i

• Lo shift è specificato tramite un registro:

il valore di R15 usato è PC_istruz.+12 © 2016

Architettura degli Elaboratori

Modo 2: esempi 42

ldr R2, [R0] @ R2 M [R0]

¬ 32 46

ldr R1, [R0,#4] [R0+4]

@ R1 M

¬ 32

ldr R1, [R0], #8 [R0]

@ R1 M

¬ 32

@ R0 R0+8

¬

ldr PC, [PC, R0, LSL #2]@ [PC+R0*4]

PC M

¬ 32

strb R7, [R9], #1 [R9] R7

@ M ¬

8 B

@ R9 R9+1

¬

str R5, [R0,#4]! @ R0 R0+4

¬

@ M [R0] R5

¬

32 © 2016

Architettura degli Elaboratori

Modo 3 (per HalfWord/signed Byte) 43

sintassi:

STR|LDR[H] Rd, <addressing_mode3> 46

LDR[SH|SB] Rd, <addressing_mode3>

può essere:

<addressing_mode3>

offset immediato

● offset da registro

● pre-incremento immediato

● pre-incremento da registro

● post-incremento immediato

● post-incremento da registro

● differenze rispetto al Modo 2:

non si possono scalare i registri

- gli offset immediati sono a soli 8bit

- © 2016

Architettura degli Elaboratori

Modo 2 e modo 3: tabella riassuntiva 44

LDR STR 46

W Modo 2 Modo 2

SH Modo 3 -

H Modo 3 Modo 3

SB Modo 3 -

B Modo 2 Modo 2

NOTA BENE: non ha senso parlare di STORE per

quantità con segno, perché non c’è alcuna estensione

del segno da effettuare © 2016

Architettura degli Elaboratori

Modo 4 (per load/store multiplo) - 1 45

sintassi:

LDM|STM <addressing_mode4> Rn{!}, <registers> 46

può essere:

<addressing_mode4>

● IA increment after

start_addr = Rn ; end_addr = Rn + #regs*4 - 4

● IB increment before

start_addr = Rn + 4 ; end_addr = Rn + #regs*4

● DA decrement after

start_addr = Rn - #regs*4 + 4 ; end_addr = Rn

DB decrement before

● start_addr = Rn - #regs*4 ; end_addr = Rn – 4

▪ (#regs è il numero di registri indicati in <registers>)

provoca l'aggiornamento del registro Rn: al suo contenuto

! viene sommata o sottratta la quantità #regs*4 © 2016

Architettura degli Elaboratori

Modo 4 (per load/store multiplo) - 2 46

sintassi:

LDM|STM <addressing_mode4> Rn{!}, <registers> 46

è la lista di registri da salvare/caricare,

<registers>

racchiusa tra parentesi graffe “{}” e con gli elementi

.

separati da virgola

esempi:

STMDB SP!, {R0-R7} @ salva sullo stack i registri da R0 a R7

LDMIA SP!, {R0-R7} @ ricarica R0-R7 salvati con l’istruzione

@ precedente

LDMDA R9, {R1,R3-R5} @ carica i registri R1, R3-R5

@ da M [R9-12].. M [R9]

32 32

Nota: indipendentemente dall’ordine con cui i registri sono specificati

all’interno delle parentesi graffe e dal suffisso (IA, IB, DA, DB), la

copia dei registri in memoria è sempre collocata ad indirizzi

crescenti con l’indice del registro. © 2016

Architettura degli Elaboratori Fine

03.a Introduzione ad ARM

e al processore S3C2440

ARM: le istruzioni assembly

03.b C. Fantozzi, A. Gardich

(revisione di S. Congiu)

Struttura programma assembly 1

La delle linee di è:

forma generale codice assembly 52

label:<sp>istruzione<sp>operandi<sp>@commento

Ogni campo deve essere separato da uno o più spazi

I label devono iniziare dal primo carattere della riga

Le istruzioni non cominciano mai dal primo carattere

della riga: devono essere precedute da almeno 1 spazio

... : ... @ ... sono opzionali

Tutti e tre le sezioni

Esistono inoltre:

direttive per l’assemblatore

● pseudo-istruzioni

● © 2016

Architettura degli Elaboratori

Direttive per l'assemblatore 2

sono comandi per l'assemblatore, non per il

direttive:

processore 52

specifica la sezione contenente il codice eseguibile

▪ .text specifica la sezione contenente dati inizializzati

▪ .data

specifica la sezione contenente dati non inizializzati

▪ .bss specifica la fine del modulo sorgente

▪ .end definisce simboli visibili al di fuori del modulo stesso:

▪ .global utile per collegare più moduli (linking)

definiscono costanti (es. in .data)

▪ .long .short .byte

definisce una stringa

▪ .ascii definiscono aree di mem. non inizializzate

▪ .lcomm .comm .skip (locali al modulo, o visibili da altri moduli)

© 2016

Architettura degli Elaboratori

Esempio di file .s 3

.text

Label .global _start

_start: 52

mov r0, #0x100 @ Inizia il programma

ciclo: subs r0, r0, #1

bne ciclo

Istruzione ldr pc, =0x112C @ esce al sistema

.data Direttiva

maschera:

.long 0xAAAAAAAA

stringa:

.ascii "Pippo"

.bss

.lcomm spazio, 100 Sezione

.end © 2016

Architettura degli Elaboratori

Classi di indirizzamento 4

Modo 1: per istruzioni di elaborazione dati

● ADC, ADD, AND, BIC, CMN, CMP, EOR, MOV, 52

MVN, ORR, RSB, RSC, SBC, SUB, TEQ, TST

Modo 2: per Load&Store di word o unsigned byte

● LDR, LDRB, STR, STRB

Modo 3: per L&S di halfword o signed byte

● LDRH, LDRSB, LDRSH, STRH

Modo 4: per L&S di registri multipli

● LDMxx, STMxx © 2016

Architettura degli Elaboratori

Modo 1 (indirizz. per elab. dati) 5

sintassi:

<istruzione3op> Rd, Rn, <shifter_operand> 52

<istruzione2op> Rd, <shifter_operand>

può essere:

<shifter_operand>

un valore immediato

● #<valore>

un registro

● Rm

un registro, dopo scorrimento specificato con:

● - un valore immediato Rm, <sop> #<shift_imm>

- un registro Rm, <sop> Rs

gli operatori disponibili sono:

● <sop>

ASR, LSL, LSR, ROR, RRX © 2016

Architettura degli Elaboratori

Modo 1: esempi 6

mov R0, #0 @ R0 0

¬ R3+1

add R3, R3, #1 @ R3 ¬ 52

(R7–1000)

cmp R7, #1000 @ cc ¬

bic R9, R8, #0xff00 @ R9 R8 and not 0xff00

¬ R0

mov R2, R0 @ R2 ¬

add R4, R3, R2 @ R4 R3+R2

¬ R0*4

mov R2, R0, LSL #2 @ R2 ¬ R5+R5*8 = R5*9

add R9, R5, R5, LSL #3 @ R9 ¬ R5–R5/8

sub R9, R5, R5, ASR #3 @ R9 ¬ R5/8–R5

rsb R9, R5, R5, ASR #3 @ R9 ¬

mov R5, R3, RRX @ R5 R3 ruotato esteso

¬

@ a destra di una posiz.

R4 ruotato a destra

mov R7, R4, ROR R3 @ R7 ¬

@ di R3 posizioni © 2016

Architettura degli Elaboratori

Modo 2 (indirizz. per Word o uns. Byte) 7

sintassi:

LDR|STR{B} Rd, <addressing_mode2> 52

è un indirizzamento indiretto

<addressing_mode2>

che può avere una delle seguenti forme:

con registro [Rn],

offset immediato

● offset da registro

● offset da registro scalato

● pre-incremento immediato

● pre-incremento da registro

● pre-incremento da registro scalato

● post-incremento immediato

● post-incremento da registro

● post-incremento da registro scalato

● © 2016

Architettura degli Elaboratori

Modo 2: offset 8

Offset immediato

● [Rn, #±<offset_12>] 52

@ Rd M[Rn ± <offset_12>]

«

Offset da registro

● [Rn, ±Rm]

@ Rd M[Rn ± Rm]

«

Offset da registro scalato

● [Rn, ±Rm, <sop> #<shift_imm>]

@ Rd M[Rn ± (Rm <sop> # <shift_imm>)]

« © 2016

Architettura degli Elaboratori

Modo 2: pre-incremento 9

Pre-incremento immediato

● [Rn, #±<offset_12>]! 52

@ Rn Rn ± <offset_12>

¬

@ Rd M[Rn]

«

Pre-incremento da registro

● [Rn, ±Rm]!

@ Rn Rn ± Rm

¬

@ Rd M[Rn]

«

Pre-incremento da registro scalato

● [Rn, ±Rm, <sop> #<shift_imm>]!

@ Rn Rn ± (Rm <sop> # <shift_imm>)

¬

@ Rd M[Rn]

« © 2016

Architettura degli Elaboratori

Modo 2: post-incremento 10

Post-incremento immediato

● [Rn], #±<offset_12> 52

@ Rd M[Rn]

«

@ Rn Rn ± <offset_12>

¬

Post-incremento da registro

● [Rn], ±Rm

@ Rd M[Rn]

«

@ Rn Rn ± Rm

¬

Post-incremento da registro scalato

● [Rn], ±Rm, <sop> #<shift_imm>

@ Rd M[Rn]

«

@ Rn Rn ± (Rm <sop> # <shift_imm>)

¬ © 2016

Architettura degli Elaboratori

Modo 2: esempi 11

ldr R2, [R0] @ R2 M [R0]

¬ 32 52

ldr R1, [R0,#4] [R0+4]

@ R1 M

¬ 32

ldr R1, [R0], #8 [R0]

@ R1 M

¬ 32

@ R0 R0+8

¬

ldr PC, [PC, R0, LSL #2]@ [PC+R0*4]

PC M

¬ 32

strb R7, [R9], #1 @ M [R9] R7

¬

8 B

@ R9 R9+1

¬

str R5, [R0,#4]! @ R0 R0+4

¬

@ M [R0] R5

¬

32 © 2016

Architettura degli Elaboratori

Modo 3 (ind. per HalfWord/signed Byte) 12

sintassi:

STR|LDR[H] Rd, <addressing_mode3> 52

LDR[SH|SB] Rd, <addressing_mode3>

può essere:

<addressing_mode3>

offset immediato

● offset da registro

● pre-incremento immediato

● pre-incremento da registro

● post-incremento immediato

● post-incremento da registro

● differenze rispetto al Modo 2:

non si possono scalare i registri

- gli offset immediati sono a soli 8bit

- © 2016

Architettura degli Elaboratori

Modo 2 e modo 3: tabella riassuntiva 13

LDR STR 52

W Modo 2 Modo 2

SH Modo 3 -

H Modo 3 Modo 3

SB Modo 3 -

B Modo 2 Modo 2

NOTA BENE: non ha senso parlare di STORE per

quantità con segno, perché non c’è alcuna estensione

del segno da effettuare © 2016

Architettura degli Elaboratori


PAGINE

629

PESO

77.85 MB

PUBBLICATO

4 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria dell'informazione
SSD:
Università: Padova - Unipd
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher miro.1998 di informazioni apprese con la frequenza delle lezioni di Architettura ed Elaboratori e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Padova - Unipd o del prof Silvestri Francesco.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria dell'informazione

Soluzioni compiti di Architettura Degli Elaboratori
Appunto
Informatica I - array bidimensionali e array paralleli
Appunto
Informatica I - la struttura dati Tabella hash con bucket
Appunto
Informatica I - Object Oriented Programming OOP e obiettivi e principi di design
Appunto