Architetture degli Elaboratori, 13 Giugno 2001


Non e' ammesso l'uso di alcun testo, appunti o calcolatrici. Le risposte ai quesiti vanno scritte nel foglio di bella copia.
Si raccomanda la massima SINTETICITA' negli esercizi che richiedano una spiegazione scritta. L'eccessiva verbosita' verra' considerata negativamente.

Per chi fa solo una o due parti per recuperare gli esoneri: Se si fa una parte sola occorre consegnare dopo 40 minuti, dopo 80 se se ne fanno due. E' possibile fare anche parti relative ad esoneri che si sono gia' sostenuti con successo, ma bisogna avvertire il docente, o chi per lui, entro 10 minuti dall'inizio dell'appello e facendo cosi' si rinuncia automaticamente al voto gia' acquisito.

Parte I


Esercizio 1
(a) Riguardo molti microprocessori si parla di backward compatibility (compatibilita'). Visto che un microprocessore puo' esser visto come la realizzazione hardware (di parte) di una macchina astratta, qual e', secondo voi, il significato di backward compatibility in termini di macchine astratte? in altre parole, cosa significa che una macchina astratta e' backward compatible?

(b) La Macchina di Turing e' alla base della nostra definizione di Macchina Astratta. Quindi una Macchina di Turing potrebbe esser vista anche come una semplicissima macchina astratta. Dire brevemente cosa fa l'interprete di una macchina di Turing.
In una macchina di Turing universale ci sono sempre due interpreti, uno, per modo di dire, "hardware", e l'altro "software". E' vero? Perche'?


Esercizio 2
Fornire l'automa a stati finiti che descriva il seguente comportamento: supponendo di avere {0,1} come possibili ingressi e uscite, si manda in output 1 quando esattamente due degli ultimi 3 input sono a 0, in tutti gli altri casi l'output sara' 0. (Si supponga che solo per il secondo input della sequenza la condizione sia "quando gli ultimi 2 bit siano a 0").

Parte II


Esercizio 3
Il cugino del noto matematico Fibonacci, tal Birbonacci, e' famoso per le sue sequenze di Birbonacci (esiste una sequenza di Birbonacci per ogni numero naturale). Gli elementi della n-esima sequenza di Birbonacci sono definiti ricorsivamente nel seguente modo :
Birb(n,0) = n
Birb(n,1) = n2
Birb(n,m) = n + ( Birb(n,m-1) * Birb(n,m-1) )
Scrivere un metodo IJVM che prenda in input due valori a e b e calcoli il b-esimo numero della a-esima sequanza di Birbonacci, in altre parole, che calcoli Birb(a,b).
Supponete di avere a disposizione un metodo per il calcolo del prodotto di due naturali.
Esercizio 4 Scrivere una bella domanda intelligente che riguardi le cache e la cui risposta sia "write through".

Parte III


Esercizio 5
(a) Riguardo ai moduli oggetto ottenuti da un assemblatore, (b) Supponiamo di avere un programma assembly che contenga la seguente istruzione (ovviamente supponiamo che il linguaggio assembly permetta istruzioni del genere)
MOV R3,#A+4096
dove A e' un simbolo, # indica la modalita' di indirizzamento immediato e R3 e' il nome di un registro.
Supponendo di avere un assemblatore a due passi, dire brevemente tutto quello che fa' l'assemblatore durante il secondo passo quando elabora questa particolare istruzione. In particolare per quello che riguarda la traduzione vera e propria dell'istruzione.

Esercizio 6
Una rete di interconnessione e' un grafo formato da che possiamo rappresentare formalmente un insieme di nodi (Nodes) ed un insieme di archi (Links) che collegano i nodi. Se consideriamo grafi non orientati, l'insieme Links degli archi puo' venire rappresentato formalmente da un insieme di sottoinsiemi di cardinalita' 2 di elementi di Nodes. Un arco che collega i nodi i e j sara' quindi denotato dall'insieme {i,j}. Supponendo, per semplicita', di considerare solo reti con insiemi di nodi di cardinalita' pari, scrivere una domanda abbastanza intelligente, la cui risposta sia:

dove b((i,j)) indica la bandwidth (ampiezza di banda) del link {i,j} e # indica la cardinalita' di un insieme.