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

  • 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.
  • 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].
  • 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. 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.

    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.