Esercizi su Formati istruzioni e Indirizzamento
Esercizio 1
Una certa macchina ha istruzioni da 16 bit e indirizzi da 6 bit.
Alcune istruzioni hanno un indirizzo, altre due.
Se ci sono n istruzioni con due indirizzi, qual'e' il numero massimo
di istruzioni ad un indirizzo?
Soluzione.
Esercizio 2
Data una macchina ad un indirizzo con accumulatore,
quali valori verranno caricati dalle seguenti istruzioni nell'accumulatore, supponendo
che la memoria contenga i valori 40, 50, 60, 70 nelle locazioni di indirizzo,
rispettivamente, 20, 30, 40, 50 ?
LOAD IMMEDIATE 20
LOAD DIRECT 20
LOAD INDIRECT 20
LOAD IMMEDIATE 30
LOAD DIRECT 30
LOAD INDIRECT 30
Soluzione.
Esercizio 3
Si confrontino le macchine a 0, 1, 2, e 3 indirizzi, scrivendo dei programmi
per calcolare
( A + B * C ) / ( D - E * F )
su ognuna delle quattro macchine. (Il risultato va messo nella locazione di indirizzo I ).
Le istruzioni disponibili all'uso sono
Ind. 0 Ind. 1 Ind.2 Ind. 4
PUSH M LOAD M MOV(X:=Y) MOV(X:=Y)
POP M STORE M ADD(X:=X+Y) ADD(X:=Y+Z)
ADD ADD M SUB(X:=X-Y) SUB(X:=Y-Z)
SUB SUB M MUL(X:=X*Y) MUL(X:=Y*Z)
MUL MUL M DIV(X:=X/Y) DIV(X:=Y/Z)
DIV DIV M
M e' un indirizzo di memoria a 16 bit e X, Y e Z sono indirizzi a 16 bit o registri
a 4 bit.
La macchina a 0 indirizzi usa uno stack (prende gli argomenti delle operazioni
dalla cima dello stack, eliminandoli, e pone il risultato sullo stack),
la macchina a 1 indirizzo usa un accumulatore e le altre hanno 16 registri e
istruzioni operanti su tutte le combinazioni di locazioni di memoria e registri.
Supponendo i codici operativi di 8 bit e lunghezze di istruzioni multipli
di 4 bit, di quanti bit avra' bisogno ciascuna macchina per calcolare il valore
dell'espressione data?
Soluzione.
Esercizio 4
Supponiamo di voler estendere la Macchina IJVM con due nuove istruzioni:
INIC e LOOP,
che facilitino la traduzione di istruzioni di ciclo presente in linguaggi
ad alto livello. Estendiamo IJVM anche con una variabile Count.
Le due istruzioni avranno il seguente formato e significato
-
INIC yyyyyyyy (Inizializza contatore per il ciclo)
con significato:
Count <- 00000000yyyyyyyy
dove la Count nella nostra realizzazione per microprogrammazione di IJVM puo' venire
realizzata utilizzando il registro OPC.
yyyyyyyy indica un numero intero senza segno di 8 bit (un numero naturale insomma)
-
LOOP yyyyyyyy (cicla finche` Count non diventa zero)
con il seguente significato:
Count <- Count-1 ;
if C>0 then goto PC+y
dove y indica uno spiazzamento rispetto al valore corrente del program
counter e deve essere interpretato come un numero di 8 bit con
segno in complemento a 2.
Scrivere il microcodice Mic-1 che realizza le due istruzioni.
Soluzione. (By P. Morreale and M. Salfi)
Esercizio 5
Scrivere un piccolo metodo JAVA la cui traduzione in IJVM potrebbe essere
semplificata dall'utilizzo delle due nuove istruzioni dell'esercizio
precedente.
Soluzione. (By P. Morreale)
Esercizio 6
Si consideri il caso in cui si voglia realizzare
un metodo che prenda in input un numero n
e che esegua n volte un certo codice.
(A) Spiegare perche', a meno di scrivere un metodo automodificante,
non sia possibile utilizzare INIC e LOOP per realizzare il metodo
di cui sopra.
(B) Dire come modificare la semantica della INIC (in pratica la sua modalita'
di indirizzamento, che nella versione proposta e' indirizzamento
immediato) per poter realizzare la procedura proposta utilizzando
senza problemi INIC e LOOP.
(C) provare a pensare come si possa realizzare, utilizzando (supponendo di averli) INIC e LOOP, un segmento di codice IJVM
che corrisponda alla traduzione del codice PASCAL seguente:
for i=1 to K do
begin
BODY
end
in particolare si discuta cosa succede se
(1)
all'interno del BODY viene utilizzata la variabile i;
(2) all'interno del BODY ci sono altre istruzioni "for" annidate.
Esercizio 7
Per ciascuna delle seguenti affermazioni, si dica se e' vera o falsa.
1. La disponibilita' di diversi metodi di indirizzamento rende piu'
complesso il formato delle istruzioni;
2. La dimensione della memoria indirizzabile influenza il formato delle
istruzioni;
3. In linea di principio, e' possibile definire il linguaggio in modo che
le istruzioni aritmetiche operino solo su registri e non su celle di memoria;
4. Il numero di operandi delle istruzioni non puo' superare il numero
dei registri indirizzabili;
5. Nelle istruzioni di salto non possono comparire, come operandi, dei registri;
6. Non si possono avere codici di istruzione di lunghezza variabile
se il set di istruzioni e' fisso.
Soluzione.
Esercizio 8
Consideriamo la macchina astratta BORDL2000, che ha 20 variabili (registri)
R1,...,R20 a 16
bit ed un indirizzamento di 2^12 word a 16 bit.
Tra le istruzioni della BORDL2000 e' un'istruzione CASN a 6 operandi che occupa complessivamente 7
word, una per l'opcode e le altre 6 per gli operandi:
CASN i op1 op2 op3 n c
Con la seguente semantica:
R[i]:=op1+m[m[op3]]+m[R[n]+c]+m[op2]
Assumere che i registri R1,...,R20 siano ospitati in memoria nelle celle m[17],...,m[36].
- Supponendo di voler realizzare BORDL2000 per intrepretazione sopra il
livello della macchina Mic-1, scrivere un segmento di codice in Mic-1 che corrisponda alla
parte di interprete che esegue l'interpretazione di tale istruzione.
Assumere che i registri R1,...,R20 siano realizzati con celle le locazioni di memoria
m[16],...,m[36].
Soluzione 1. (By Max Salfi)
Soluzione 2 (by E. Papotto & Maurizio Morgano ?)
Esercizio 9
Si dica, motivando la risposta, se sia possibile progettare una macchina
con le seguenti caratteristiche:
formato istruzione: 16 bit
numero di registri indirizzabili: 8
numero di parole di memoria: 1024
7 istruzioni con 1 operando in memoria e 1 operando registro
15 istruzioni con 3 operandi registri
8 istruzioni con 2 operandi registri
Una possibile soluzione.
Esercizio 10
Una macchina ha le seguenti caratteristiche:
Dimensione istruzioni: 32 bit
Numero registri indirizzabili: 8
Numero celle : 4K
Si intende progettare un codice ad espansione per codificare il seguente
insieme di istruzioni:
31 istruzioni con due indirizzi di memoria e un indirizzo di registro;
7 istruzioni con due indirizzi di memoria;
n istruzioni con un indirizzo di memoria ed un indirizzo di registro.
Quale e' il valore massimo di n?
Soluzione.
Esercizio 11
Dire perche' qualsiasi istruzione che utilizzi un modo di indirizzamento immediato
richiede un tempo di esecuzione minore di qualsiasi istruzione che utilizzi un modo
di indirizzamento indiretto.
Soluzione.
Esercizio 12
Fare gli esercizi 1, 2, 3, 4, 5, 7, 8 del Capitolo 5 del Tananbaum.
Soluzione 1. (By Calcagno, Tomasello and Zito)
Soluzione 2. (By Musumarra and Barnaba')
Soluzione 3. (By Firrincieli and Di Odoardo)
Soluzione 5. (By Zisa Alessandro)
Soluzione 8. (By Tomasello Calcagno Zito)
Esercizio 13
Una macchina ha le seguenti caratteristiche:
Dimensione istruzioni: formato variabile
Numero registri indirizzabili: 13
Numero celle : 43K
E' possibile progettare un codice ad espansione per codificare il seguente
insieme di istruzioni?
7 istruzioni con due indirizzi di memoria e un indirizzo di registro;
31 istruzioni con due indirizzi di memoria;
63 istruzioni con tre indirizzi di memoria.
Soluzione. (By Peppe Monreale)
Esercizio 14
Dire quali sono le modalita' di indirizzamento utilizzate per le seguenti istruzioni
IJVM: BIPUSH, DUP, IADD, IINC. Dire quale istruzioni di IJVM utilizzano
l'indirizzamento diretto.
Soluzione.
Esercizio 15
(a)
Cosa significa che in un linguaggio di livello ISA c'e' ortogonalita'
tra opcodes e modalita' di indirizzamento?
C'e' ortogonalita' in IJVM? Perche'?
(b)
Qual e' la modalita' di indirizzamento utilizzata nelle istruzioni GOTO e INVOKEVIRTUAL
di IJVM?
Soluzione.
Esercizio 16
(a)
Dovremmo cambiare molte cose nella IJVM, ed eventualmente cosa, se pretendessimo che la modalita'
di indirizzamento per entrambi gli argomenti dell'istruzione IINC sia
puro indirizzamento diretto?
(b)
L'istruzione IRETURN ha una modalita' di indirizzamento?
Se si, quale? Se no, perche'?
Soluzione.
Esercizio 17
Riscrivere il programma di Fig. 5-17 supponendo di avere a disposizione
anche la modalita' di indirizzamento Indexed.
Fare un esempio di programmino, sullo stile di quelli di Fig. 5-17 e 5-18,
per cui risulti utile l'utilizzo della modalita' di indirizzamento
Based-Indexed.
Esercizio 18
Consideriamo il seguente frammento di programma (descritto anche
nel Tananbaum) scritto in un linguaggio assembly generico.
MOV R1,#0 ; accumula l'OR in R1, inizialmente 0
MOV R2,#0 ; R2=indice, i, del prodotto: A[i] AND B[i]
MOV R3,#4096 ; R3=indice del primo valore da non usare
LOOP: MOV R4,A(R2) ; R4=A[i]
AND R4,B(R2) ; R4=A[i] AND B[i]
OR R1,R4 ; OR tutti i prodotti booleani in R1
ADD R2,#4 ; i=i+4 (una parola alla volta =4byte)
CMP R2,R3 ; finito?
BLT LOOP ; se R2 < R3, non abbiamo finito, quindi continua.
Tale programma suppone di avere in memoria due vettori di 1024 parole.
Tali vettori sono memorizzati a partire dagli indirizzi A e B.
Ogni parola e' lunga 4 byte e l'indirizzamento della memoria e' al byte.
Il programma calcola, per ogni parola del vettore A, l'AND bit a bit di tale parola con
la parola corrispondente in B, per poi fare l'OR bit a bit di tutte le 1024 parole ottenute.
Riscrivere il codice supponendo di avere a disposizione tutte le modalita' di indirizzamento
utilizzate nel programma dato, escluso l'indirizzanento indice, supponendo
pero' di avere a disposizione anche l'indirizzamento indiretto dei registri,
che si denota con (r), dove r e' il nome di un registro.
Ricordiamo che #c denota indirizzamento immediato, r quello registro e c(r) quello
indice.
Ricordate che il primo argomento delle istruzioni e' anche quello dove
finisce il risultato.
Soluzione.
Esercizio 19
(esercizio 3 del capitolo 5 del Tanenbaum)
E' possibile progettare un codice ad espansione che permetta la codifica di quanto segue
in una istruzione di 12 bit? Un registro viene indicato con 3 bit.
-
4 istruzioni con tre registri
-
255 istruzioni con un registro
-
16 istruzioni con zero registri
Giustificare la risposta.
Soluzione.
Esercizio 20
Consideriamo il seguente frammento di programma (descritto anche
nel Tananbaum) scritto in un linguaggio assembly generico.
MOV R1,#0 ; accumula l'OR in R1, inizialmente 0
MOV R2,#0 ; R2=indice, i, del prodotto: A[i] AND B[i]
MOV R3,#4096 ; R3=indice del primo valore da non usare
LOOP: MOV R4,A(R2) ; R4=A[i]
AND R4,B(R2) ; R4=A[i] AND B[i]
OR R1,R4 ; OR tutti i prodotti booleani in R1
ADD R2,#4 ; i=i+4 (una parola alla volta =4byte)
CMP R2,R3 ; finito?
BLT LOOP ; se R2 < R3, non abbiamo finito, quindi continua.
Tale programma suppone di avere in memoria due vettori di 1024 parole.
Tali vettori sono memorizzati a partire dagli indirizzi A e B.
Ogni parola e' lunga 4 byte e l'indirizzamento della memoria e' al byte.
Il programma calcola, per ogni parola del vettore A, l'AND bit a bit di tale parola con
la parola corrispondente in B, per poi fare l'OR bit a bit di tutte le 1024 parole ottenute.
Riscrivere, se possibile, il codice supponendo di avere a disposizione solamente
indirizzamento registro, diretto e immediato.
Ricordiamo che #c denota indirizzamento immediato e si supponga che
c puo' essere un numerale, un simbolo
o un'espressione matematica formata da questi.
Ricordiamo che l'indirizzamento registro e diretto si denota con c e si supponga che
c puo' essere solo il nome di un registro, un numerale o un simbolo.
Se riscrivere il codice con i vincoli proposti non fosse possibile, fornire
una giustificazione di questo fatto.
Si puo' supporre, volendo, la presenza di altri registri nella macchina oltre a
quelli presenti nel codice dato.
Ricordate che il primo argomento delle istruzioni e' anche quello dove
finisce il risultato.
Soluzione.
Esercizio 21
E' possibile progettare un codice ad espansione che permetta la codifica di quanto segue
in una istruzione di 12 bit? Un registro viene indicato con 3 bit.
4 istruzioni con tre registri
258 istruzioni con un registro
8 istruzioni con zero registri
Giustificare la risposta.
Soluzione.
Esercizio 22
Descrivere un problemino di programmazione che non si puo'
risolvere utilizzando le sole modalita' di indirizzamento immediato e registro.
E che invece si risolve con quella registro indiretta.
Soluzione.
Esercizio 23
Consideriamo il seguente esempio di formato delle istruzioni di una macchina a due indirizzi
Bits 8 3 5 4 3 5 4
_______________________________________________________
| OPCODE | MODE | REG | OFFSET | MODE | REG | OFFSET |
-------------------------------------------------------
: (optional 32-bit direct address or offset) :
.......................................................
: (optional 32-bit direct address or offset) :
.......................................................
Supponiamo che l'opcode dell'istruzione MOV che sposta il contenuto
di locazioni di memoria/registri in locazioni di memoria/registri sia 01010101
Fornire delle stringhe di 32 bit che rappresentano le
due seguenti istruzioni
MOV #3 4
MOV (R4) R6
Dove #n rappresenta la modalita' immediata, Rn quella registro,
(Rn) quella registro indiretta e n quella diretta.
Le modalita' di indirizzamento sono codificate nel seguente modo:
000 immediata,
001 diretta,
010 registro,
011 registro indiretta,
100 indice.
Soluzione.
Esercizio 24
È possibile progettare un codice ad espansione che permetta la
codifica di quanto segue in una istruzione di 12 bit? Un registro viene
indicato con 3 bit.
- 4 istruzioni con
tre registri
- 255 istruzioni
con un registro
- 8 istruzioni con
zero registri
Giustificare la risposta.
N.B. ovviamente per istruzione a tre (uno, zero) registri si intende
un?istruzione con tre (uno, zero) argomenti, tutti specificati con modalità
registro.
Soluzione.
Esercizio 24
Il formato delle microistruzioni Mic-1 e' a lunghezza fissa o variabile?
Qual e' il vantaggio che si ha? e lo svantaggio? Stesse domande per le istruzioni IJVM.
Esercizio 25
Consideriamo il seguente frammento di programma (descritto anche
nel Tananbaum) scritto in un linguaggio assembly generico.
MOV R1,#0
MOV R2,#0
MOV R3,4096
LOOP: MOV R4,(R2)
AND R4,(R2)
OR R1,A(R4)
ADD R2,4(B)
CMP R2,R3
BLT LOOP
Tale programma suppone di avere in memoria due vettori di 1024 parole.
Tali vettori sono memorizzati a partire dagli indirizzi A e B.
Ogni parola e' lunga 4 byte e l'indirizzamento della memoria e' al byte.
Il programma dovrebbe calcolare, per ogni parola del vettore A,
l'AND bit a bit di tale parola con
la parola corrispondente in B, per poi fare l'OR bit a bit di tutte le 1024 parole ottenute.
Il programma in realta' contiene degli errori relativamente alle modalita' di
indirizzamento utilizzare. Identificare tali errori e correggerli.
Ricordiamo che #c denota indirizzamento immediato, dove
c puo' essere un numerale, un simbolo
o un'espressione matematica formata da questi.
L'indirizzamento registro e diretto si denota con c, dove
c puo' essere solo il nome di un registro, un numerale o un simbolo.
L'indirizzamento registro indiretto si denota con (R), mentre l'indirizzamento
indicizzato (indexed addressing) si denota con L(R).
Ricordate che il primo argomento delle istruzioni e' anche quello dove
finisce il risultato.
Esercizio 26
Cosa si intende per modalita' di indirizzamento? Descrivere brevemente le
principali modalita' di indirizzamento ed il loro uso.
Esercizio 27
Supponiamo di voler introdurre in IJVM un certo livello di Ortogonalita' tra
opcodes (codici operativi) e modalita' di indirizzamento.
Per esempio, vogliamo che IADD possa lavorare con due differenti
modalita' di indirizzamento: stack e immediato.
I due byte successivi ad IADD indicheranno le modalita' di indirizzamento
degli operandi, a cui seguiranno 0, 1, o 2 byte nel caso ci siano 0, 1 o due operandi
con modalita' immediata. Il byte 0x00 indichera' indirizzamento a stack,
il byte 0x01 quello immediato. Il risultato sara' sempre inserito in cima allo
stack. Gli operandi a stack verranno eliminati dallo stack.
Scrivere il microcodice Mic-2 (Due!) che implementa questa nuova versione
di IADD.
Soluzione.
Esercizio 28
Discutere brevemente dei Criteri progettuali per i formati d'istruzioni del livello ISA.
Esercizio 29
Uno dei principi di progettazione dei calcolatori moderni e'
"Le istruzioni devono essere facili da decodificare".
In che modo e' possibile soddisfare tale requisito?
E' un requisito da rispettare solo per linguaggi realizzati in Hw?
Giustificare.
Esercizio 30
Descrivere le piu' comuni modalita' di indirizzamento, indicando
(fornendo giustificazione)
quali istruzioni IJVM lavorano eventualmente con tali modalita'.
Esercizio 31
Si consideri il seguente generico programma assembly per il calcolo
della somma degli elementi di un array di 1024 interi memorizzati
a partire dall'indirizzo A (ogni intero e' memorizzato in una parola di 4 byte).
Riscrivere tale programma utilizzando anche la modalita' di indirizzamento indicizzato (Indexed addressing).
MOV R1,#0 ;aggiorna la somma in R1, posto inizialmente a 0
MOV R2,#A ;R2=indirizzo dell'array A
MOV R3,#A+4096 ;R3=indirizzo della prima parola dopo l'array
ciclo ADD R1,(R2) ;recupera l'operando attraverso R2, registro indiretto
ADD R2,#4 ;incrementa R2 di una parola (4 byte)
CMP R2,R3 ;abbiamo gia' finito?
BLT ciclo ;se R2 < R3 non abbiamo finito, quindi si continua
L'indirizzamento indicizzato si indica con C(R), dove C e' una costante ed R un registro.
Soluzione.
Esercizio 32
Cos'e' un codice a espansione con configurazione di espansione?
Perche' puo' risultare utile utilizzare tali codici per rappresentare
i codici operativi di un linguaggio macchina?
Fare il seguente esercizio relativo a tali codici.
Una macchina ha le seguenti caratteristiche:
Dimensione istruzioni: 32 bit
Numero registri indirizzabili: 8
Numero celle di memoria : 4K
Si intende progettare un codice ad espansione (codice operativo espandibile)
per codificare il seguente
insieme di istruzioni:
31 istruzioni con due indirizzi di memoria e un indirizzo di registro;
7 istruzioni con due indirizzi di memoria;
n istruzioni con un indirizzo di celle di memoria ed un indirizzo di registro.
Dire, giustificando, qual e' il valore massimo di n.
Soluzione.