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

Calcolatori Elettronici II (A-L)

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).

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 X_i, Y_i, Z_i, con 0 <= i < N. Dopo aver determinato Z_i = GCD(X_i,Y_i) per ciascun valore di i, la subroutine restituisce anche il numero di coppie (X_i,Y_i) 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.)