Calcolatori Elettronici II - Testi d'esame

Università di Roma "La Sapienza" - Corso di Laurea in Ingegneria Informatica

Calcolatori Elettronici II

Testi d'esame

Anno accademico 2001/2002 (canale A-L)
Esonero del 28 giugno 2002
Appello del 9 luglio 2002
Appello del 23 luglio 2002
Appello del 9 settembre 2002
Appello del 13 dicembre 2002

Anno accademico 2002/2003 (canale A-L)
Esonero del 19 giugno 2003
Appello del 7 luglio 2003
Appello del 21 luglio 2003
Appello del 10 settembre 2003
Appello del 9 dicembre 2003

Anno accademico 2003/2004 (canale M-Z)
Esonero dell'8 giugno 2004
Appello del 28 giugno 2004
Appello del 9 luglio 2004
Appello del 13 settembre 2004
Appello del 17 dicembre 2004

Anno accademico 2004/2005 (canale A-L)
Appello del 6 luglio 2005
Appello del 20 luglio 2005
Appello del 14 settembre 2005
Appello del 16 dicembre 2005

Anno accademico 2005/2006 (canale A-L)
Esonero del 19 giugno 2006
Appello del 6 luglio 2006
Appello del 15 luglio 2006
Appello del 14 settembre 2006
Appello del 21 dicembre 2006
Appello del 13 aprile 2007


Calcolatori Elettronici II (A-L) - Prova di esonero - 28/06/2002

Università degli Studi di Roma "La Sapienza" – Corso di Laurea in Ingegneria Informatica

Calcolatori Elettronici II (A-L)

Prova di esonero (28 giugno 2002)

Cognome e nome ____________________________________________________
Matricola _____________________

L'interfaccia IFMAX riceve in continuazione da un bus esterno EXTDATA0-15 dati numerici paralleli a 16 bit in complemento a 2, sincronizzati a un clock esterno EXTCLK con frequenza 1 MHz. Su comando dalla CPU PD32, IFMAX esamina un blocco di 256 dati consecutivi, calcola il massimo Vmax dei valori presenti nel blocco, e trasmette il risultato alla CPU. A sua volta, la CPU mantiene in una variabile VMINMAX il minimo dei valori Vmax ricevuti.

Progettare l'interfaccia IFMAX e codificare il relativo software di pilotaggio.

Last update 2003-12-10 01:20


Calcolatori Elettronici II (A-L) - Sessione estiva - Appello del 9 luglio 2002

Università degli Studi di Roma "La Sapienza" - Corso di Laurea in Ingegneria Informatica
a.a. 2001-2002

Calcolatori Elettronici II (A-L)
Sessione estiva - Appello del 9 luglio 2002

Prima prova (15 punti)

Un'interfaccia IFRANGE è connessa a un bus esterno EXTDATA0-15 su cui transitano dati numerici paralleli sincronizzati a un clock esterno EXTCLK. IFRANGE riceve dalla CPU PD32 due valori numerici Vmin e Vmax, quindi avvia l'acquisizione di una sequenza di 1024 dati EXTDATA, determina il numero N di valori della sequenza compresi nell'intervallo [Vmin, Vmax], e trasmette tale risultato alla CPU. Quest'ultima confronta il valore ricevuto di N con un valore di soglia N0 e:

  • decrementa Vmin e incrementa Vmax se N < N0
  • incrementa Vmin e decrementa Vmax se N > N0

dopo di che riavvia il processo.

Progettare l'interfaccia IFRANGE e codificare il relativo software di pilotaggio.

Seconda prova

  1. (5 punti) Descrivere la struttura e il funzionamento di una cache set-associativa a 4 vie, con lunghezza di blocco da 16 byte.
  2. (5 punti) Descrivere l'implementazione pipeline dell'istruzione Jump And Link (JAL) nella CPU MIPS, individuando gli eventuali conflitti e discutendone le relative soluzioni.
  3. (5 punti) Enunciare la legge di Amdahl, discutere le sue implicazioni e descriverne un esempio di applicazione.

Last update 2003-12-10 01:20


Calcolatori Elettronici II (A-L) - Appello del 23 luglio 2002

a.a. 2001-2002

Sessione estiva - Appello del 23 luglio 2002

Prima prova (15 punti)

Un'interfaccia SERIN riceve in continuazione dal mondo esterno parole a 12 bit su una linea seriale XDATA, sincronizzate a un clock XCLK e a un segnale XSYNC:

020723.gif (2626 bytes)

dove il bit 0 è il bit meno significativo della parola. SERIN assembla i dati ricevuti e li invia in formato parallelo alla CPU PD32, che li dispone in un buffer circolare da 1024 word allocato all'indirizzo 7000000h.

Progettare l'interfaccia SERIN e codificare il relativo software di pilotaggio.

Seconda prova

  1. (5 punti) Si voglia estendere il set di istruzioni della CPU MIPS con l'istruzione Add Memory in formato I:
    addm $rt,offset($rs)    ; rt ¬ (rt) + Memory[offset+(rs)]
    Discutere le varianti all'architettura multiciclo della CPU necessarie per l'implementazione di tale istruzione e determinarne il diagramma degli stati per il controllo dell'esecuzione.
  2. (5 punti) Una cache set-associativa ad N vie, con blocchi da B byte, ha una capacità totale di C byte di dati (tag esclusi). La CPU ad essa connessa opera con indirizzi da k bit e con dati da 32 bit. Determinare in funzione di k, N, B, C:
    • il numero di set in cui è suddivisa la cache,
    • il numero totale di bit necessari per l'immagazzinamento dei tag,
    • le funzioni e le dimensioni dei vari campi in cui viene suddiviso l'indirizzo nell'accesso alla cache.
    (Si assuma che N, B, C siano tutte potenze intere di 2, e si trascurino nel calcolo i bit di validità, dirty, etc.)
  3. (5 punti) Un sistema di memoria virtuale ha le seguenti caratteristiche: indirizzo virtuale da 36 bit, pagine fisiche da 4 Kbyte, memoria fisica da 1 Gbyte. Assumendo il byte come minima unità indirizzabile, descrivere il meccanismo di paginazione corrispondente, e determinare le dimensioni della Page Table. (Si trascuri lo spazio necessario per i bit di validità, dirty, protezione, etc.; si trascuri anche lo spazio necessario per le informazioni di puntamento al disco rigido.)

Last update 2003-12-10 01:20


Calcolatori Elettronici II (A-L) - Sessione estiva - Appello del 9 settembre 2002

a.a. 2001-2002

Sessione estiva - Appello del 9 settembre 2002

Prima prova (15 punti)

Una CPU PD32 preleva dati a 12 bit da un buffer circolare da 2048 word e li trasmette ad una interfaccia SEROUT, che li serializza su una linea XDATA sincronizzandoli a un clock XCLK, generato internamente all'interfaccia; il bit meno significativo (bit 0) di ciascuna parola da 12 bit viene emesso per primo, ed è identificato da un segnale XSYNC, anch'esso generato da SEROUT:

020909.gif (2626 bytes)

Le linee XDATA, XCLK, XSYNC vengono poi inviate al mondo esterno.

Progettare l'interfaccia SEROUT e codificare il relativo software di pilotaggio.

Seconda prova

  1. (5 punti) Il carico medio giornaliero di un sistema di elaborazione è ripartito per il 35% sulla CPU, per il 45% sulla memoria e per il 20% sul disco rigido (il carico su altri sottosistemi può essere considerato trascurabile). In vista di un possibile upgrade del sistema, sono disponibili le seguenti opzioni:
    Opzione
    n.         		Sottosistema
    sostituito         		Accelerazione
    del sottosistema         		Costo della
    sostituzione
    (in euro)
    1 | CPU | 25% | 550
    2 | Memoria | 15% | 200
    3 | Disco rigido | 20% | 150

Quale delle suddette opzioni è da preferire, e per quali ragioni?

  2. (5 punti) Si voglia estendere il set di istruzioni della CPU MIPS con l'istruzione Jump Indirect in formato I:

jm offset($rs)      ; PC ¬ Memory[offset+(rs)]

Discutere le varianti all'architettura multiciclo della CPU necessarie per l'implementazione di tale istruzione, e determinarne il diagramma degli stati per il controllo dell'esecuzione.

  3. (5 punti) Discutere i vantaggi e gli svantaggi derivanti dall'introduzione di un secondo livello di cache.

Last update 2003-12-10 01:20


Calcolatori Elettronici II (A-L) - Appello del 13 dicembre 2002

a.a. 2001-2002

Appello del 13 dicembre 2002

Prima prova (15 punti)

Una periferica IFPTY acquisisce dati paralleli da 16 linee XD0-15, sincronizzati ad un segnale esterno XSTROBE:

021213-1.gif (1195 bytes)

IFPTY verifica la parità di ciascun dato (ossia che il numero dei bit uguali ad 1 sia pari) e, se il dato è corretto, lo invia alla CPU PD-32, la quale lo accoda in un buffer da 4096 word. Al completamento del buffer, la CPU legge da IFPTY il numero di errori riscontrati, dopo di che avvia un nuovo ciclo di acquisizione.

Progettare l'interfaccia IFPTY e codificare il relativo software di pilotaggio.

Seconda prova

1. (5 punti) In un sistema di elaborazione la memoria principale e la memoria di massa sono utilizzate rispettivamente per il 50% e per il 20% del tempo di esecuzione. Per rendere il sistema più efficiente, vi è la possibilità di:

  1. sostituire il banco di memoria principale con uno più veloce del 25%, oppure
  2. sostituire la memoria di massa con una il doppio più veloce.

Quale delle due alternative è da preferire, e perché?

2. (5 punti) Discutere i vari tipi di conflitti che possono aver luogo in una CPU pipeline e i metodi adottati per risolverli.

3. (5 punti) Descrivere la struttura e il funzionamento di una cache set-associativa a 4 vie, con lunghezza di blocco da 32 byte.

Last update 2003-12-10 01:20


Calcolatori Elettronici II (A-L) - Esonero del 19 giugno 2003

a.a. 2002-2003

Esonero del 19 giugno 2003

Prova unica (15 punti)

Un'interfaccia IFTEMP acquisisce misure di temperatura da 16 sensori termici e controlla l'accensione e lo spegnimento di altrettanti elementi riscaldanti; i dati di temperatura sono espressi come valori da 8 bit in complemento a 2. L'interfaccia contiene inoltre un timer da 5 secondi, asservito al clock della CPU PD-32 che ha frequenza 100 MHz.

Ogni 5 secondi la CPU esegue un ciclo completo di acquisizione e controllo, che consiste nel confrontare la temperatura Ti misurata dall'i-esimo sensore (0 £ i < 16) con due valori di soglia residenti in memoria Mi, Ni (dove Mi < Ni) e nel controllare lo stato dell'i-esimo elemento riscaldante secondo le regole seguenti:

  • se Ti > Ni, l'i-esimo elemento riscaldante viene spento;
  • se Ti < Mi, l'i-esimo elemento riscaldante viene acceso;
  • altrimenti, lo stato dell'i-esimo elemento riscaldante rimane invariato.

Si progetti l'hardware dell'interfaccia e si codifichi il relativo software di gestione.

Last update 2003-12-10 01:20


Calcolatori Elettronici II (A-L) -- Appello del 7 luglio 2003

a.a. 2002-2003

Appello del 7 luglio 2003

Prima prova (15 punti)

Un'interfaccia IFRTC (Real Time Clock) utilizza un generatore interno di clock a 32 kHz per mantenere un orologio in tempo reale con le seguenti informazioni: anno, mese, giorno, ore, minuti, secondi, millisecondi.

Il driver software residente sulla CPU PD-32 è strutturato in due subroutine, GET_RTC e SET_RTC, ciascuna delle quali accetta come argomento un puntatore a un blocco di dati da 10 byte così strutturato:

La subroutine GET_RTC legge dall'interfaccia le informazioni di data/ora corrente e riempie il blocco, mentre la subroutine SET_RTC utilizza le informazioni trovate nel blocco per inizializzare l'orologio.

Descrivere la struttura hardware dell'interfaccia IFRTC (assumendo che gli anni esattamente divisibili per 4 siano sempre bisestili) e codificare le due subroutine di pilotaggio.

Seconda prova

1. (5 punti) Descrivere i conflitti che possono aver luogo in una CPU organizzata in pipeline e discutere i metodi utilizzati per eliminarli o ridurne gli effetti.

2. (5 punti) In una CPU con clock a 250 MHz, il 30% del tempo di esecuzione di un programma è utilizzato per accessi alla memoria, ognuno dei quali richiede 6 cicli di clock. Supponendo che tra CPU e memoria venga interposta una cache con i seguenti parametri:

  • Hit Time = 1 ciclo di clock
  • Miss Penalty = 12 cicli di clock
  • Miss Rate = 5%

stimare l'aumento della velocità di esecuzione del programma stesso.

3. (5 punti) Descrivere le sequenze di eventi che, a seconda del successo o del fallimento nel reperire i dati, possono aver luogo nel corso di un accesso alla memoria virtuale da parte di una CPU in presenza di Translation Lookaside Buffer (TLB) e di cache.


Calcolatori Elettronici II (A-L) -- Appello del 21 luglio 2003

a.a. 2002-2003

Appello del 21 luglio 2003

Prima prova (15 punti)

Una periferica IFKEY contiene una memoria a sola lettura (ROM) organizzata in 220 parole da 56 bit, dove ogni parola è suddivisa in un campo chiave (KEY) da 24 bit e un campo informazione (INFO) da 32 bit; le parole nella ROM sono ordinate per valori crescenti di KEY. La periferica riceve dalla CPU PD-32 un valore KEY ed esegue una ricerca nella ROM; se tale chiave viene trovata, restituisce alla CPU il corrispondente valore del campo INFO, altrimenti restituisce 00000000h.

Progettare l'hardware della periferica, e codificare una subroutine che gestisce la ricerca attraverso IFKEY e riceve come argomenti:

  • un puntatore a una tavola KEYTABLE contenente un elenco di chiavi per ciascuna delle quali eseguire la ricerca;
  • il numero di elementi della tavola suddetta;
  • un puntatore a una tavola INFOTABLE nella quale la stessa subroutine dispone ordinatamente le informazioni restituite dalla periferica per ciascuna chiave presente in KEYTABLE.

Seconda prova

1. (5 punti) Misurazioni effettuate su un sistema di elaborazione indicano che il 40% del tempo viene utilizzato per accessi alla memoria principale e il 30% per transazioni sul disco rigido, il quale ha un tempo medio di accesso pari a 3.6 millisec. Per adeguare il sistema a sopraggiunte nuove esigenze, si decide di sostituire la memoria principale con una più veloce del 50%, e di rimpiazzare il disco rigido con uno di capacità quadrupla ma con tempo medio di accesso leggermente superiore, pari a 4 millisec. Come varieranno le prestazioni del sistema?

2. (5 punti) Si consideri l'istruzione MIPS-32 Jump And Link Register:

jalr $rd, $rs

che esegue un salto incondizionato alla subroutine il cui indirizzo è contenuto nel registro $rs dopo aver salvato l'indirizzo di ritorno nel registro $rd. Mostrare quali modifiche vanno apportate all'architettura base della CPU in versione pipeline per implementare tale istruzione, e discutere gli eventuali conflitti che ne conseguono.

3. (5 punti) Descrivere l'architettura di una cache set-associativa a 4 vie, con capacità di 256 KByte (tag esclusi) e lunghezza di blocco pari a 4 parole da 32 bit.


Calcolatori Elettronici II (A-L) -- Appello del 10 settembre 2003

a.a. 2002-2003

Appello del 10 settembre 2003

Prima prova (15 punti)

Una periferica IFCLK, dedicata alla visualizzazione dell'ora corrente, contiene un modulo Timer (Fig. 1) mediante il quale essa invia interruzioni alla CPU PD-32 con cadenza di uno al secondo. In risposta all'interrupt, la CPU mantiene in memoria il conteggio dell'ora corrente, espresso in ore/minuti/secondi, e lo presenta su un dispositivo di visualizzazione (Fig. 2) residente sulla periferica stessa. Tale dispositivo è a sua volta costituito da 6 display a sette segmenti, ciascuno dei quali (Fig. 3) è utilizzato per la visualizzazione di una singola cifra decimale ed è dotato di 7 ingressi digitali che controllano direttamente l'accensione o lo spegnimento dei rispettivi segmenti.

fig1.gif (2300 bytes)
Fig. 1

fig2.gif (5439 bytes)
Fig. 2

fig3.gif (4372 bytes)
Fig. 3

Progettare l'hardware della periferica IFCLK, e codificare il software per l'aggiornamento e la presentazione delle informazioni di ore/minuti/secondi.

Seconda prova

1. (6 punti) Ricavare un'espressione per la legge di Amdahl generalizzata, che determini l'accelerazione totale A di un sistema nel quale vengano sostituite N componenti, ciascuna con un suo bi (frazione del tempo di utilizzo) e con una sua Ai (accelerazione della componente).

2. (5 punti) Come variano le prestazioni di una cache all'aumentare del numero di parole per blocco?

3. (4 punti) Un sistema di memoria virtuale ha le seguenti caratteristiche: indirizzo virtuale da 34 bit, pagine fisiche da 4 Kbyte, memoria fisica da 2 Gbyte. Assumendo il byte come minima unità indirizzabile, descrivere il meccanismo di paginazione corrispondente. Determinare quindi le dimensioni della Page Table, trascurando lo spazio necessario sia per i bit di validità, dirty, protezione, etc., che per le informazioni di puntamento alla memoria di massa.


Calcolatori Elettronici II (A-L) -- Appello del 9 dicembre 2003

a.a. 2002-2003

Appello del 9 dicembre 2003

Prima prova (15 punti)

Progettare un DMA Controller per il trasferimento di dati dalla memoria del PD-32 verso il mondo esterno in modo che la CPU abbia la possibilità di definire, con l'invio di opportuni comandi al Controller stesso:

  • l'ampiezza delle parole trasferite: byte, word, oppure doubleword;
  • il verso di scansione dell'area di memoria interessata: per indirizzi crescenti, oppure decrescenti;
  • la modalità di trasferimento: a burst oppure in cycle stealing.

Seconda prova

1. (5 punti) Descrivere l'architettura di una cache set-associativa a 2 vie, con capacità di 512 KByte (tag e bit di controllo esclusi) e lunghezza di blocco pari a 8 parole da 32 bit.

2. (5 punti) Si voglia implementare l'istruzione MIPS branch on greater or zero and link
bgezal $rs, offset
in cui viene testato il registro $rs: se il suo contenuto risulta maggiore o uguale a zero, il valore corrente del Program Counter viene salvato nel registro $r31 e viene quindi eseguito il branch all'offset specificato, relativamente al Program Counter; altrimenti, l'esecuzione procede in sequenza.

Stabilire se e quali varianti all'architettura pipeline della CPU siano necessarie per l'implementazione di tale istruzione, ed evidenziare il flusso dei dati nelle varie fasi della sua esecuzione.

3. (5 punti) Per ciascuna delle seguenti affermazioni, contrassegnare la casella [V] o la casella [F] a seconda che essa sia considerata vera o, rispettivamente, falsa:

V
F
Una CPU con frequenza di clock da 400 MHz è dotata di cache con hit time = 1 clock e miss penalty = 8 clock; allora il tempo medio di accesso alla memoria è maggiore di 23 nanosecondi.
V
F
La tecnica di memory mapped I/O può essere utilizzata soltanto con quelle CPU che non dispongono di istruzioni di input/output.
V
F
Il Page Table Register contiene la lunghezza della Page Table.
V
F
La sequenza di istruzioni MIPS

xor $r3,$r1,$r2
xor $r2,$r2,$r3
xor $r1,$r1,$r3

scambia tra loro i contenuti dei registri $r1 , $r2 .

V
F
Una cache usa modalità di scrittura di tipo write back. Allora per ogni blocco valido B in essa presente esiste sempre una copia di B anche in memoria principale.


Calcolatori Elettronici II (M-Z) -- Esonero dell'8 giugno 2004

a.a. 2003-2004

Calcolatori Elettronici II (M-Z)

Esonero dell'8 giugno 2004

Prova unica (15 punti)

Una periferica IFPER riceve un segnale esterno XSIG avente periodo variabile da 0.5 a 4 microsec, ed esegue misure di periodo su tale segnale utilizzando il System Clock a 200 MHz come base dei tempi.

Progettare l'hardware della periferica e codificare una subroutine di pilotaggio mediante cui la CPU PD-32 acquisisce 16 misurazioni consecutive p0, p1, ... , p15 dalle quali calcola

  • la media delle misure:

040608-1.gif (626 bytes)

  • la media dei valori assoluti degli scarti:

040608-2.gif (719 bytes)


Calcolatori Elettronici II (M-Z) -- Appello del 28 giugno 2004

a.a. 2003-2004

Calcolatori Elettronici II (M-Z)

Appello del 28 giugno 2004

Prima prova (15 punti)

Una periferica IFSTR riceve dall'esterno dati seriali attraverso una linea XDATA e un clock XCLK. La CPU PD-32, dopo aver inviato alla periferica un numero N < 4096 e un dato a 12 bit S = s11s10...s1s0, attiva l'acquisizione di una stringa binaria T costituita da N bit consecutivi prelevati dalla linea XDATA. Al termine dell'acquisizione, IFSTR comunica alla CPU:

  • il numero A di sottostringhe S = s11s10...s1s0 trovate all'interno della stringa T;
  • il numero B di sottostringhe S' = s0s1...s10s11 trovate all'interno della stringa T.

Progettare l'hardware della periferica IFSTR e codificare il software di controllo sotto forma di subroutine che accetta in ingresso il puntatore ad una tavola residente in memoria e organizzata come segue:

NPTR
SPTR
APTR
BPTR

dove

  • NPTR e SPTR sono i puntatori alle locazioni che contengono il numero N e il dato S da trasmettere a IFSTR;
  • APTR e BPTR sono i puntatori alle locazioni dove andranno immagazzinati i numeri A e B ottenuti da IFSTR.

Seconda prova

1. (5 punti) Descrivere l'architettura di una cache set-associativa a 4 vie, con capacità di 1 MByte (tag e bit di controllo esclusi) e lunghezza di blocco pari a 4 parole da 32 bit.

2. (5 punti) Si voglia implementare l'istruzione MIPS Set on Less Than

slt $rd, $rs, $rt

in cui nel registro $rd viene scritta la costante 1 o la costante 0 a seconda che sia verificata o meno la relazione ($rs) < ($rt).

Determinare quali varianti all'architettura pipeline della CPU siano necessarie per l'implementazione di tale istruzione.

3. (5 punti) Per ciascuna delle seguenti affermazioni, contrassegnare la casella [V] o la casella [F] a seconda che essa sia considerata vera o, rispettivamente, falsa:

V
F
Il Translation Lookaside Buffer (TLB) è una cache per gli elementi della Page Table più recentemente utilizzati.
V
F
Una Interrupt Service Routine (ISR) non può mai essere interrotta dallo stesso interrupt che l'ha mandata in esecuzione.
V
F
La strategia di scrittura più frequentemente usata nei sistemi di memoria virtuale è quella di tipo write-through.
V
F
La sequenza di istruzioni PD-32

XORL R1,R2
XORL R2,R1
XORL R1,R2

scambia tra loro i contenuti dei registri R1, R2.

V
F
In una cache a capacità costante, il miss rate è inversamente proporzionale alla lunghezza del blocco.


Calcolatori Elettronici II (M-Z) -- Appello del 9 luglio 2004

a.a. 2003-2004

Calcolatori Elettronici II (M-Z)

Appello del 9 luglio 2004

Prima prova (15 punti)

Una periferica IFDISP è connessa a 8 canali di comunicazione, ciascuno dei quali è costituito da 16 linee dati in uscita e due segnali di handshake (Fig. 1).

040709-1.gif (1136 bytes)
Fig. 1

All'arrivo di una richiesta di servizio XREQ da parte di un qualsiasi canale (Fig. 2):

  • la periferica segnala l'evento alla CPU PD-32;
  • il software di pilotaggio di IFDISP estrae un dato a 16 bit da una coda circolare da 4 Kbyte residente in memoria e lo consegna alla periferica;
  • la periferica trasmette il dato alle linee XDATA del canale che ne aveva fatto richiesta, e attiva nel contempo la linea XRDY dello stesso canale (Fig. 2) notificando in tal modo il completamento del servizio.

040709-2.gif (901 bytes)
Fig. 2

Progettare l'hardware della periferica e codificare il relativo software di pilotaggio, corredandolo di adeguati commenti.

Seconda prova

1. (5 punti) In un sistema di elaborazione la memoria di massa è utilizzata per il 70% del tempo. Di quanto occorrerà aumentare la velocità di tale unità affinché le prestazioni del sistema aumentino del 100%?

2. (5 punti) Discutere i vari conflitti che possono aver luogo in una CPU organizzata in pipeline e le tecniche usate per risolverli.

3. (5 punti) Discutere la funzione del Translation Lookaside Buffer (TLB) nei sistemi di memoria virtuale e descriverne l'organizzazione.


Calcolatori Elettronici II (M-Z) -- Appello del 9 luglio 2004

a.a. 2003-2004

Calcolatori Elettronici II (M-Z)

Appello del 13 settembre 2004

Prima prova (15 punti)

Una periferica IFBCD (Fig. 1) riceve dati a 4 bit dalle linee XIN0-3 sincronizzati a un clock XCLK. Un messaggio su tali linee è costituito dalla sequenza di dati:

  • 1111 (intestazione del messaggio)
  • 0xxx (interpretato come un numero k, 0 £ k < 8)
  • da una a quattro cifre BCD (Binary Coded Decimal)
  • 1110 (termine del messaggio)

Per ogni messaggio ricevuto, la periferica converte le cifre BCD ricevute in un numero binario N a 16 bit (la prima cifra BCD ricevuta è la più significativa, si veda l'esempio in Fig. 2) e invia il risultato al canale di uscita XOUT k0-15 identificato dal numero k contenuto nel messaggio.

Inoltre, il numero k e il numero N vengono inviati alla CPU PD-32, la quale aggiorna una tavola, residente in memoria, in cui per ciascun canale di uscita XOUT vengono mantenuti il minimo e il massimo dei numeri N ad esso inviati.

040913-1.gif (1741 bytes)
Fig. 1 		040913-2.gif (1714 bytes)
Fig. 2

Progettare l'hardware della periferica e codificare il relativo software di pilotaggio, corredandolo di adeguati commenti.

Seconda prova

1. (5 punti) In vista dell'upgrade di una procedura software, che viene eseguita in 55 secondi, sono disponibili le seguenti opzioni per la revisione di alcune sue componenti:
Opzione | Tempo di esecuzione prima della revisione | Tempo di esecuzione dopo la revisione | Costo della revisione (in Euro)
Routine n. 1 | 12 sec | 9 sec | 2000
Routine n. 2 | 15 sec | 11 sec | 3000
Routine n. 3 | 22 sec | 17 sec | 4000

Per ragioni di costo, è possibile sostituire solo due delle tre componenti indicate; quale sarà in tal caso la combinazione migliore sotto l'aspetto del rapporto prestazioni/costo?

2. | (5 punti) Descrivere i conflitti di controllo nelle CPU dotate di pipeline e discutere i metodi per la loro risoluzione.
3. | (5 punti) Si abbiano a disposizione due cache: la prima, ad accesso diretto, ha miss rate del 30% e miss penalty pari a 60 cicli di clock; nella seconda, di tipo set-associativo, il miss rate si riduce del 10% mentre il miss penalty aumenta del 10%. Se l'hit time è lo stesso nei due casi, quale delle due cache fornisce le migliori prestazioni?


Calcolatori Elettronici II (M-Z) -- Appello del 17 dicembre 2004

a.a. 2003-2004

Calcolatori Elettronici II (M-Z)

Appello del 17 dicembre 2004

Prima prova (15 punti)

Una periferica IFSPK per CPU PD-32 produce messaggi audio sintetizzati verso un canale di uscita costituito da 8 linee di output XD0-7 e da un clock esterno XCLK da 8 kHz. Un messaggio è costituito da una sequenza di campioni audio da 8 bit, che vengono applicati alle linee XD0-7 e sincronizzati con XCLK. Una memoria ROM, residente sulla periferica e organizzata in 16M parole da 8 bit, contiene i campioni relativi a 256 messaggi, nessuno dei quali ha durata di emissione superiore ai 10 secondi.

La subroutine di controllo di IFSPK accetta in ingresso un numero N (0 £ N < 256) che identifica un messaggio da emettere, e che viene utilizzato come indice in una tavola residente nella memoria del sistema; ogni elemento della tavola contiene l'indirizzo iniziale del messaggio corrispondente nella ROM e il numero di campioni da cui esso è costituito. La subroutine comanda quindi la selezione del messaggio sulla periferica e l'emissione del messaggio stesso, e ritorna al chiamante solo ad emissione completata.

Progettare l'hardware della periferica e codificare il relativo software di pilotaggio, corredandolo di adeguati commenti.

Seconda prova

1. | (5 punti) Una cache set-associativa a 4 vie e blocchi da 4 parole da 32 bit riceve indirizzi a 32 bit, 15 dei quali vengono utilizzati come campo tag. Determinare la capacità totale in byte della cache (bit di controllo e tag esclusi) e il numero totale di bit richiesti per l'immagazzinamento dei tag.
2. | (5 punti) Se in un sistema viene sostituita una componente A, le prestazioni del sistema aumentano del 20%; se invece viene sostituita un'altra componente B, le prestazioni aumentano del 30%. Di quanto aumentano le prestazioni se vengono sostituite entrambe le componenti A e B?
3. | (5 punti) Discutere i conflitti di controllo che possono aver luogo in una CPU organizzata in pipeline, e descrivere i metodi per la loro risoluzione.


Calcolatori Elettronici II (A-L) -- Appello del 6 luglio 2005

a.a. 2004-2005

Appello del 6 luglio 2005

Prima prova (15 punti)

Un'interfaccia IFABS riceve in continuazione da un bus externo XDATA0-15 dati numerici paralleli a 16 bit in complemento a 2, sincronizzati a un clock esterno XCLK. Su comando della CPU, IFABS procede all'acquisizione di un blocco da 1024 dati, dei quali calcola il massimo e il minimo dei valori assoluti:

A = maxi | xi | B = mini | xi |

Questi due risultati vengono quindi trasmessi alla CPU che calcola il valore

U = A + B
2

e aggiorna le seguenti locazioni di memoria:

  • AMIN con il minimo tra tutti i valori A acquisiti;
  • BMAX con il massimo tra tutti i valori B acquisiti;
  • UMIN e UMAX col minimo e, rispettivamente, il massimo tra tutti i valori U calcolati.

Progettare l'hardware della periferica e codificare il relativo software di pilotaggio, corredandolo di adeguati commenti.

Seconda prova

1. | (5 punti) Descrivere l'architettura di una cache set-associativa a 4 vie, con capacità di 1 MByte (tag e bit di controllo esclusi) e lunghezza di blocco pari a 4 parole da 32 bit.
2. | (5 punti) Descrivere i conflitti di controllo nelle CPU dotate di pipeline e discutere i metodi per la loro risoluzione.
3. | (5 punti) Discutere la funzione del Translation Lookaside Buffer (TLB) nei sistemi di memoria virtuale e descriverne l'organizzazione.


Calcolatori Elettronici II (A-L) - Appello del 20 luglio 2005

a.a. 2004-2005

Appello del 20 luglio 2005

Prima prova (15 punti)

Un'interfaccia IFGCD, che opera come coprocessore per il calcolo del massimo comun divisore (greatest commmon divisor, GCD), riceve dalla CPU PD-32 una coppia (X,Y) di numeri interi assoluti a 32 bit e calcola Z = GCD(X,Y) secondo l'algoritmo di Euclide, dove X e Y sono entrambi non nulli e REM(X,Y) rappresenta il resto della divisione intera di X per Y:

  1. Si determina R = REM(X,Y).
  2. Se R = 0, l'algoritmo termina con Z = Y come risultato.
  3. Se R = 1, i due numeri sono mutuamente primi e l'algoritmo termina con Z = 1 come risultato; altrimenti, la coppia di valori (X,Y) viene sostituita dalla coppia (Y,R), e si torna al passo (1).

Il calcolo della funzione R = REM(X,Y) viene realizzato mediante un apposito modulo sequenziale (Fig. 1) in cui l'inizio e il termine delle operazioni sono determinati dai segnali presenti rispettivamente all'ingresso BEGIN e all'uscita END (Fig. 2).

050720-1.gif (4146 bytes)
Fig. 1

050720-2.gif (3965 bytes)
Fig. 2

Il software di pilotaggio dell'interfaccia è organizzato sotto forma di subroutine che accetta in ingresso un intero N e i puntatori a tre tavole di interi assoluti a 32 bit Xi, Yi, Zi, con 0 <= i < N. Dopo aver determinato Zi = GCD(Xi,Yi) per ciascun valore di i, la subroutine restituisce anche il numero di coppie (Xi,Yi) mutuamente prime trovate nel corso dell'esecuzione.

Progettare l'hardware dell'interfaccia e codificare la relativa subroutine di pilotaggio, corredandola di adeguati commenti.

Seconda prova

1. (5 punti) Se in un programma si sostituisce una sua subroutine A, la sua velocità aumenta del 25%; se invece si sostituisce un'altra sua subroutine B, la velocità aumenta del 35%. Di quanto aumenterà la velocità del programma, se si sostituiscono entrambe le subroutine A e B?

2. (5 punti) Si consideri l'istruzione MIPS-32 Jump and Link Register:

jalr $rd, $rs

che esegue un salto incondizionato alla subroutine il cui indirizzo è contenuto nel registro $rs dopo aver salvato l'indirizzo di ritorno nel registro $rd. Illustrare quali modifiche vanno apportate all'architettura base della CPU in versione pipeline per l'implementazione di tale istruzione, e discutere gli eventuali conflitti che ne conseguono.

3. (5 punti) Un sistema di memoria virtuale opera con indirizzi virtuali a 36 bit, indirizzi fisici a 32 bit e pagine da 8 Kbyte. Di quanti bit sarà la capacità totale del Translation Lookaside Buffer (TLB) se questo è organizzato come cache totalmente associativa da 128 linee? (Si comprendano nel calcolo solo i campi tag e dati, escludendo i bit di controllo: validità, dirty, etc.)


Calcolatori Elettronici II (A-L) - Appello del 14 settembre 2005

a.a. 2004-2005

Appello del 14 settembre 2005

Prima prova (15 punti)

Un'interfaccia IFRLE riceve in continuazione da un bus esterno XDAT0-7 dati paralleli a 8 bit, sincronizzati a un clock esterno XCLK e a un segnale XSYNC che individua l'inizio di un blocco di 4096 dati.

050914htm.gif (8826 bytes)

L'interfaccia comprime il blocco con un algoritmo di run-length encoding in cui una sequenza di N byte uguali consecutivi di valore X viene trasformata nella coppia di byte { X, N }; se N > 255, la sequenza viene suddivisa nel minimo numero di sottosequenze di lunghezza inferiore a 256, ciascuna codificata come sopra. Ad esempio, la sequenza { 23 23 23 23 23 } viene codificata come { 23 05 }, mentre una sequenza di 1000 byte uguali a 37 viene codificata come { 37 255 37 255 37 255 37 235 }.

Il software di controllo su CPU PD-32 è organizzato come subroutine che:

  • accetta come argomenti il puntatore a un buffer e la sua lunghezza;
  • avvia la compressione di un blocco di dati;
  • acquisisce i risultati della compressione e li dispone ordinatamente nel buffer;
  • restituisce al chiamante il numero di byte scritti nel buffer, oppure il valore 0 se la dimensione del buffer è insufficiente a contenere i risultati della compressione.

Progettare l'hardware dell'interfaccia e codificare la relativa subroutine di pilotaggio, corredandola di adeguati commenti.

Seconda prova

1. (5 punti) Una CPU opera con clock da 200 MHz e con una cache ad accesso diretto avente hit time pari a un singolo ciclo di clock e miss penalty di 300 nsec. In tali condizioni, le misurazioni forniscono un tempo medio di accesso alla memoria di 125 nsec. Se la cache ad accesso diretto viene sostituita con una di tipo set-associativo, in cui il miss rate diminuisce del 30%, di quanto migliorerà il tempo medio di accesso alla memoria?
2. (5 punti) Si voglia estendere il set di istruzioni della CPU MIPS con l'istruzione Jump Indirect in formato I:

jm offset($rs)      ; PC ¬ Memory[offset+($rs)]

Discutere le varianti all'architettura multiciclo della CPU necessarie per l'implementazione di tale istruzione, e determinarne il diagramma degli stati per il controllo dell'esecuzione.
3. (5 punti) Una cache set-associativa ad N vie, con blocchi da B byte, ha una capacità totale di C byte di dati (tag esclusi). La CPU ad essa connessa opera con indirizzi da k bit e con dati da 32 bit. Determinare in funzione di k, N, B, C:
  • il numero di set in cui è suddivisa la cache,
  • il numero totale di bit necessari per l'immagazzinamento dei tag,
  • le funzioni e le dimensioni dei vari campi in cui viene suddiviso l'indirizzo nell'accesso alla cache.

(Si assuma che N, B, C siano tutte potenze intere di 2, e si trascurino nel calcolo i bit di validità, dirty, etc.)


Calcolatori Elettronici II (A-L) - Appello del 16 dicembre 2005

a.a. 2004-2005

Appello del 16 dicembre settembre 2005

Prima prova (15 punti)

Un'interfaccia IFSUM comprende:

  • un modulo di tastiera (Fig. 1a) che, alla pressione di un tasto, genera un codice a 4 bit K3-0 corrispondente al carattere impresso sul tasto e un impulso di validazione KSTB (Fig. 1b);

    051216-1.gif (8020 bytes)

    Fig. 1

  • un modulo di display a 12 caratteri (Fig. 2a) che accetta in ingresso un codice di posizione DP3-0 (il carattere più a sinistra ha posizione 0, quello più a destra ha posizione 11), un codice di carattere DD3-0 e un impulso di validazione DSTB (Fig. 2b); l'attivazione di DSTB produce la visualizzazione del carattere dato nella posizione specificata.

    051216-2.gif (9332 bytes)

    Fig. 2

I codici utilizzati sono i normali codici BCD per i caratteri numerici, più le combinazioni 1010 per il simbolo + e 1011 per il simbolo =; la combinazione 1111 viene inoltre accettata dal display come codice di cancellazione.

L'utente imposta due o più operandi numerici separati dal segno + e conclude l'operazione premendo il tasto =; l'interfaccia IFSUM trasmette le informazioni relative alla CPU PD-32, la quale, oltre a presentare sul display i caratteri quando vengono impostati su tastiera, esegue le operazioni di somma richieste e visualizza il risultato sul display. Se il risultato supera le 12 cifre, vengono presentati 12 simboli +.

Progettare l'hardware per l'interfacciamento dei moduli al bus della CPU e codificare il relativo software di pilotaggio, corredandolo di adeguati commenti.

Seconda prova

1. (5 punti) In un sistema di elaborazione la memoria di massa è utilizzata per il 75% del tempo. Di quanto occorrerà aumentare la velocità di tale unità affinché le prestazioni del sistema aumentino del 60%?
2.

(5 punti) Si voglia implementare l'istruzione MIPS-32 Branch on EQual And Link

beqal $rs, offset

in cui viene testato il registro $rs: se il suo contenuto risulta uguale a zero, il valore corrente del Program Counter viene salvato nel registro $r31 e viene quindi eseguito il branch all'offset specificato, relativamente al Program Counter; altrimenti, l'esecuzione procede in sequenza. Stabilire se e quali varianti all'architettura pipeline della CPU siano necessarie per l'implementazione di tale istruzione, ed evidenziare il flusso dei dati nelle varie fasi della sua esecuzione.
3. (5 punti) Descrivere l'architettura di una cache set-associativa a 2 vie, con capacità di 2 MByte (tag e bit di controllo esclusi) e lunghezza di blocco pari a 8 parole da 32 bit; evidenziare inoltre i vari campi in cui viene suddiviso l'indirizzo applicato alla cache e discutere la loro funzione.


Calcolatori Elettronici II (A-L) - Esonero del 19 giugno 2006

a.a. 2005-2006

Esonero del 19 giugno 2006

Prova unica (15 punti)

Un'interfaccia IFRNG riceve in continuazione da un bus externo XDATA0-15 dati paralleli a 16 bit, da interpretare come valori numerici assoluti, sincronizzati a un clock esterno XCLK. La CPU PD-32, dopo aver inviato all'interfaccia due valori numerici M ed N, comanda l'acquisizione di un blocco di 4096 dati consecutivi xi (0 £ i < 4096) dalle linee XDATA; l'interfaccia genera tre valori numerici P, Q, R tali che:

  • P è il conteggio dei valori xi tali che xi < M;
  • Q è il conteggio dei valori xi tali che M £ xi £ N;
  • R è il conteggio dei valori xi tali che N < xi.

I tre risultati P, Q, R vengono quindi trasmessi alla CPU, che li dispone ordinatamente in una tavola RTABLE residente in memoria.

Progettare l'hardware dell'interfaccia IFRNG e codificare il relativo software di pilotaggio sotto forma di subroutine, corredandolo di adeguati commenti.


Calcolatori Elettronici II (A-L) - Appello del 6 luglio 2006

a.a. 2004-2005

Appello del 6 luglio 2006

Prima prova (15 punti)

Un'interfaccia IFCMP opera come coprocessore per l'esecuzione di moltiplicazioni tra numeri complessi, rappresentati come coppie ordinate di numeri reali floating-point a 64 bit. L'interfaccia riceve dalla CPU PD-32 due operandi complessi X = XR + j XI, Y = YR + j YI, dove j = Ö(-1) è l'unità immaginaria, e trasmette alla CPU il risultato

Z = ZR + j ZI = (XR YR - XI YI) + j (XR YI + XI YR)

L'hardware dell'interfaccia utilizza un singolo modulo sequenziale FPMA (Floating-Point Multiply/Add, Fig. 1) per l'esecuzione dell'operazione R = A + B C, dove A, B, C, R sono numeri reali floating-point a 32 bit; l'inizio e il termine delle operazioni del modulo sono determinati dai segnali presenti rispettivamente all'ingresso BEGIN e all'uscita END (Fig. 2).

060706-1.gif (2837 bytes)

Fig. 1 		060706-2.gif (2217 bytes)

Fig. 2

Il software di pilotaggio è organizzato sotto forma di subroutine che riceve in ingresso:

  • un intero N > 0
  • i puntatori a due tavole XTABLE, YTABLE, che contengono rispettivamente N numeri complessi X[i] ed N numeri complessi Y[i]
  • il puntatore a una tavola ZTABLE nella quale, dopo l'esecuzione dei calcoli necessari, dovranno essere immagazzinati gli N risultati Z[i] = X[i] Y[i]

Progettare l'hardware dell'interfaccia e codificare la relativa subroutine di pilotaggio, corredandola di adeguati commenti.

NOTE:

  • Il modulo FPMA non deve essere progettato.
  • Il valore 0, qualora necessario, è rappresentato in floating-point come 32 bit tutti uguali a zero.

Seconda prova

1. | (5 punti) Descrivere l'organizzazione di una cache set-associativa a 4 vie, con capacità di 4 MByte (tag e bit di controllo esclusi) e lunghezza di blocco pari a 8 parole da 32 bit; evidenziare inoltre i vari campi in cui viene suddiviso l'indirizzo a 32 bit applicato alla cache e discutere la loro funzione.
2. | (5 punti) Un programma viene eseguito in 2.1 secondi; una sua subroutine, che viene richiamata 70 volte nel corso del programma, richiede un tempo di esecuzione di 10 millisecondi. Se la subroutine viene riscritta in modo da risultare il 75% più veloce, di quanto aumenterà la velocità dell'intero programma?
3. | (5 punti) Descrivere le circostanze in cui si verificano conflitti di dati in una CPU MIPS-32 organizzata in pipeline, e discutere le tecniche per ridurre o eliminare gli stalli che ne conseguono.


Calcolatori Elettronici II (A-L) - Appello del 16 dicembre 2005

a.a. 2005-2006

Appello del 15 luglio 2006

Prima prova (15 punti)

Un'interfaccia IFSEQ riceve in continuazione dall'esterno dati seriali attraverso una linea XDAT e un clock XCLK (Fig. 1).

060715-1.gif (1733 bytes)

Fig. 1

Su comando della CPU PD-32, l'interfaccia avvia l'acquisizione di una stringa binaria S costituita da 1024 bit consecutivi prelevati dalla linea XDAT; al termine, l'interfaccia trasmette alla CPU i seguenti dati:

  • il numero di bit P della più lunga sottosequenza di S tutta costituita da 0;
  • il numero di bit Q della più lunga sottosequenza di S tutta costituita da 1.

Il software di controllo dell'interfaccia, organizzato come subroutine, avvia una singola acquisizione al termine della quale utilizza i valori restituiti dall'interfaccia per aggiornare due tavole PTABLE e QTABLE definite come:

  • PTABLE[j] contiene il numero di acquisizioni che hanno restituito P = j;
  • QTABLE[k] contiene il numero di acquisizioni che hanno restituito Q = k.

Progettare l'hardware dell'interfaccia IFSEQ e codificare il relativo software di controllo, corredandolo di adeguati commenti.

Seconda prova

1. | (5 punti) Si consideri l'istruzione MIPS-32 Jump and Link Register: jalr $rd, $rs che esegue un salto incondizionato alla subroutine il cui indirizzo è contenuto nel registro $rs salvando l'indirizzo di ritorno nel registro $rd. Illustrare quali modifiche vanno apportate all'architettura base della CPU in versione pipeline per l'implementazione di tale istruzione, e discutere gli eventuali conflitti che ne conseguono.
2. | (5 punti) Se in un sistema viene sostituita una componente A, le prestazioni del sistema aumentano del 15%; se viene sostituita una diversa componente B, le prestazioni aumentano del 20%; se infine viene sostituita una terza componente C, le prestazioni aumentano del 25%. Di quanto aumentano le prestazioni del sistema se vengono sostituite tutte e tre le componenti A, B e C?
3. | (5 punti) Un sistema di memoria virtuale ha le seguenti caratteristiche: indirizzo virtuale da 36 bit, pagine fisiche da 8 Kbyte, memoria fisica da 4 Gbyte. Assumendo il byte come minima unità indirizzabile, descrivere il meccanismo di paginazione corrispondente. Determinare quindi le dimensioni della Page Table, trascurando lo spazio necessario sia per i bit di validità, dirty, protezione, etc., che per le informazioni di puntamento alla memoria di massa.


Calcolatori Elettronici II (A-L) - Appello del 14 settembre 2006

a.a. 2005-2006

Appello del 14 settembre 2006

Prima prova (15 punti)

Un'interfaccia IFMVP opera come coprocessore per il calcolo di prodotti matrice-vettore y = Mx, dove x = { xi ≤ 0 = < 4 } e y = { yi, 0 ≤ i < 4 } sono vettori a 4 componenti e M = { Mij, 0 ≤ i, j < 4 }è una matrice 4×4; sia le componenti dei vettori che gli elementi della matrice sono numeri floating-point a 64 bit. L'interfaccia riceve dalla CPU PD-32 un vettore x e un intero k che identifica una tra 256 matrici M immagazzinate in una ROM residente sulla stessa interfaccia, e restituisce alla CPU il vettore prodotto y tale che

 | 3 |
yi = | Σ | Mij xj
 | j=0 |

Per l'esecuzione dei calcoli relativi, l'interfaccia utilizza un singolo modulo FPMA (Floating-Point Multiply Add, Fig. 1) per l'esecuzione dell'operazione R = A + BC, dove A, B, C, R sono numeri reali floating-point a 64 bit; tale operazione viene completata in un tempo non superiore a 4 periodi di System Clock.

FPMA module

Fig. 1

Il software di pilotaggio è organizzato sotto forma di subroutine che riceve in ingresso:

  • un intero N > 0
  • i puntatori a due tavole KTABLE, XTABLE che contengono rispettivamente N interi k identificatori di matrice e N vettori x;
  • il puntatore a una tavola YTABLE nella quale, dopo l'esecuzione dei calcoli necessari, dovranno essere immagazzinati gli N vettori y risultanti.

Progettare l'hardware dell'interfaccia e codificare la subroutine di pilotaggio, corredandola di adeguati commenti.

Seconda prova

1. | (5 punti) Una CPU opera con clock da 250 MHz e con una cache ad accesso diretto avente hit time pari a un singolo ciclo di clock e miss penalty di 450 nsec. In tali condizioni, le misurazioni forniscono un tempo medio di accesso alla memoria di 125 nsec. Se la cache ad accesso diretto viene sostituita con una di tipo set-associativo, in cui il miss rate diminuisce del 25%, di quanto migliorerà il tempo medio di accesso alla memoria?
2. | (5 punti) Un sistema di memoria virtuale ha le seguenti caratteristiche: indirizzo virtuale da 34 bit, pagine fisiche da 4 Kbyte, memoria fisica da 2 Gbyte. Assumendo il byte come minima unità indirizzabile, descrivere il meccanismo di paginazione corrispondente, e determinare le dimensioni della Page Table. (Si trascuri lo spazio necessario per i bit di validità, dirty, protezione, etc.; si trascuri anche lo spazio necessario per le informazioni di puntamento al disco rigido.)
3. | (5 punti) Si voglia estendere il set di istruzioni della CPU MIPS con l'istruzione Subtract Memory in formato I: subm $rt,offset($rs) ; $rt ← ($rt) - Memory[offset+(rs)] Discutere le varianti all'architettura multiciclo della CPU necessarie per l'implementazione di tale istruzione e determinarne il diagramma degli stati per il controllo dell'esecuzione.


Calcolatori Elettronici II - Appello del 21 dicembre 2006

a.a. 2005-2006

Appello del 21 dicembre 2006

Prima prova (15 punti)

Un'interfaccia IFMED riceve una sequenza continua {xn} di numeri binari assoluti a 8 bit dalle linee esterne XDAT[0-7], sincronizzate a un clock XCLK. La sequenza {xn} viene sottoposta a un processo di filtraggio non lineare, noto come median filter, nel quale ciascun valore di uscita {yn} viene determinato ordinando la terna {xn, xn-1, xn-2} per valori crescenti ed estraendo il secondo elemento dell'insieme così ottenuto. Ad esempio:

I termini della sequenza di uscita {yn}, oltre ad essere avviati verso un gruppo di linee di uscita XOUT[0-7], devono anche essere confrontati con un valore di soglia T fornito dalla CPU PD-32, e deve essere generato un interrupt ogni volta che yn > T.

Il software di controllo deve:

  • estrarre un valore di soglia da una locazione di memoria THRESHOLD e inviarlo all'interfaccia;
  • inizializzare un contatore COUNTER da 32 bit residente in memoria;
  • incrementare COUNTER ogni volta che il valore di soglia viene superato.

Progettare l'hardware dell'interfaccia e codificare il software di pilotaggio, corredandolo di adeguati commenti.

Seconda prova

1. (5 punti) Una CPU opera con clock da 200 MHz e con una cache avente Hit Time = 1 clock e Miss Penalty = 8 clock; in tali condizioni, il tempo medio di accesso ai dati in memoria è pari a 21 nsec. Inserendo nel sistema anche una cache di secondo livello, avente lo stesso Hit Time ma Miss Penalty = 16 clock, si osserva un miglioramento del 26.5% nel tempo medio di accesso. Stimare il Miss Rate per ciascuna delle due cache.
2. (5 punti) Si voglia implementare l'istruzione MIPS-32 Branch on Greater Than And Link

bgtal $rs, offset

in cui viene testato il registro $rs: se il suo contenuto risulta maggiore di zero, il valore corrente del Program Counter viene salvato nel registro $r31 e viene quindi eseguito il branch all'offset specificato, relativamente al Program Counter; altrimenti, l'esecuzione procede in sequenza.

Stabilire quali varianti all'architettura pipeline della CPU siano necessarie per l'implementazione di tale istruzione, ed evidenziare il flusso dei dati nelle varie fasi della sua esecuzione.
3. (5 punti) Discutere la funzione del Translation Lookaside Buffer (TLB) nei sistemi di memoria virtuale e descriverne l'organizzazione.


Calcolatori Elettronici II (A-L) - Appello del 13 aprile 2007

a.a. 2005-2006

Appello del 13 aprile 2007

Prima prova (15 punti)

Un'interfaccia IFMSG, attestata sul bus di I/O di una CPU PD-32, riceve in continuazione dati a 8 bit da un canale esterno XDAT[0-7] sincronizzati a un clock XCLK. Un messaggio su tale canale è costituito da una sequenza di byte consecutivi tali che:

  • il primo byte (header) identifica l'inizio del messaggio ed è sempre uguale a FFh;
  • il secondo byte è un numero D, con 0 <= D < 128, da interpretare come destinazione;
  • il terzo byte è un numero L, con 0 < L < 128, che indica la lunghezza del messaggio;
  • seguono L byte che costituiscono il corpo del messaggio.

Tra un messaggio e l'altro sul canale sono presenti solo byte uguali a 00h.

Su comando della CPU l'interfaccia aspetta l'arrivo di un messaggio e trasferisce ad essa le relative informazioni, come specificato più avanti.

Il software di controllo deve essere organizzato come subroutine che:

  • riceve nel registro R0 il puntatore a una tavola da 128 elementi, il cui elemento di indice k contiene il puntatore all'area di memoria in cui dovrà essere memorizzato il corpo del messaggio avente destinazione k;
  • avvia l'acquisizione di un messaggio.

Al termine dell'acquisizione, la subroutine pone nei registri R1 e R2 la destinazione D e, rispettivamente, la lunghezza L del messaggio acquisito, e ritorna infine al chiamante.

Progettare l'hardware dell'interfaccia e codificare il software di pilotaggio, corredandolo di adeguati commenti.

Seconda prova

1. | (5 punti) Descrivere l'organizzazione di una cache set-associativa a 4 vie, con blocchi da 16 byte e indirizzi a 32 bit; determinarne poi la capacità totale in bit, includendo i tag e trascurando i campi di controllo (validità, dirty, etc.)
2. | (5 punti) In un sistema di elaborazione la memoria di massa e la memoria principale sono utilizzate rispettivamente per il 15% e per il 60% del tempo di esecuzione. Per rendere il sistema più efficiente, vi è la possibilità di: (a) sostituire la memoria principale con una il 20% più veloce, con un certo costo X, oppure (b) sostituire la memoria di massa con una il doppio più veloce, con un costo 3X. Quale delle due alternative è da preferire, e perché?
3. | (5 punti) Descrivere le circostanze in cui si verificano conflitti di dati in una CPU MIPS-32 organizzata in pipeline, e discutere le tecniche per ridurne l'impatto sulle prestazioni.