Cognome ESATTO Nome GIUSTO Matricola A

ARCHITETTURA DEGLI ELABORATORI 1 - Seconda prova intermedia - 23 giugno 2003

1) Un dispositivo DM, gestito ad interrupt, genera periodicamente richieste di interruzioni con periodo Tm; la sua RSI ha durata (complessiva) Rm=100 µs. Un secondo dispositivo DP, più prioritario di DM, ha una RSI di durata (complessiva) Rp=20 µs e può interrompere DM al massimo una volta durante ciascun periodo Tm. Per non perdere dati di DM, il minimo valore di Tm è:

TmMIN=120 µs Poiché è noto che DP può interrompere la RSI di DM al più una sola volta tra due successive richieste di interruzione di quest’ultimo, questa RSI può terminare al più tardi dopo: Tdm = DurataRsiDm+DurataRsiDp dalla prima delle due richieste di DM (DP introduce, con la sua RSI, un ritardo che si aggiunge al tempo necessario all’esecuzione della RSI di DM). Pertanto Tdm è anche il periodo minimo di DM: TmMIN = Tdm = 100+20 = 120 µµµµs

2) Un dispositivo D1 trasferisce, via DMA, blocchi da 1000 dati ciascuno. Per comandare il trasferimento di un blocco vengono eseguite dalla CPU 3 istruzioni la cui durata complessiva corrisponde a 10 cicli di bus, la RSI attivata dopo il trasferimento dell’ultimo dato del blocco ha una durata corrispondente a 200 cicli di bus (ciascun ciclo di bus dura 70 ns). Il tempo di CPU complessivamente impegnato per il trasferimento di uno dei blocchi (includendo il ritardo dovuto ad accessi DMA di D1) è al massimo pari a TDMA µs.

TDMA = 84.7 µs L’impegno della CPU nei confronti di D1 include le istruzioni iniziali, il ritardo complessivo dovuto al fenomeno di cycle stealing durante il trasferimento in DMA, che è al massimo pari al numero di cicli occupati da quel trasferimento (1 ciclo per ogni dato), e l’esecuzione della RSI. TDMA = (CicliIstrIniz + NumDati + CicliRSI) * PeriodoCiclo = (10+1000+200)*70 = 84700 ns = 84.7 µµµµs

3) Un ADC può funzionare sia ad interrupt che in DMA: nel primo caso (una richiesta d’interruzione per dato), la RSI ha una durata complessiva di 10 µs, nel secondo caso (una richiesta d’interruzione per blocco di dati), essendo il numero di dati di ogni blocco molto elevato, la durata della RSI è trascurabile. Sapendo che il ciclo di bus ha una durata di 200ns e supponendo di tollerare in entrambi i casi una occupazione massima del tempo di CPU dedicato al dispositivo del 2% (trascurando la RSI del DMA), allora il periodo minimo con cui possono essere trasferiti i dati gesti-ti ad interrupt è TI; quello con cui possono essere trasferiti i dati via DMA è TD.

TI = 500µs

TD = 10µs In caso di gestione ad interrupt, l’occupazione di tempo di CPU è dovuta all’esecuzione di una attiva-zione della routine di servizio ogni periodo del dispositivo. Pertanto risulta: (DurataRsi / TI ) * 100 = PercentualeOccupazione TI = (DurataRSI / PercentualeOccupazione) * 100 = 1000 / 2 = 500 µµµµs In caso di gestione in DMA, l’occupazione ‘equivalente’ è dovuta al cycle stealing. Pertanto risulta: (DurataCiclo / TD ) * 100 = PercentualeOccupazione TD = (DurataCiclo / PercentualeOccupazione) * 100 = 20000 / 2 = 10000 ns = 10 µµµµs

4) Un sistema PD32 è dotato di una instruction cache e di una data cache completamente associative; ciascuna delle due cache contiene 16 blocchi da 32 byte. A data cache vuota, viene eseguito il segmento di codice che segue, caricato in memoria a partire dall’indirizzo $400. Immaginando che la data cache adotti un criterio di rimpiazzo di tipo LRU (Least Recently Used), quando viene eseguita l’istruzione NOP la percentuale di hit sul totale degli accessi alla data cache è pari a ph.

MOVL #$A, R0 MOVL #$1000, R1 LOOP: MOVL (R1), R2

ANDL #$FFE, R2

MOVL R2, (R1)+

SUBL #1, R0

JNZ LOOP

NOP ph= 90 %

Nella domanda la cache coinvolta è solo quella dei dati. Il codice effettua una lettura dalla memoria nella terza istruzione (la prima del ciclo) e una scrittura nella quinta (la terza del ciclo); le altre istru-zioni contengono dati immediati, letti quindi dall’altra cache durante la fase di fetch, o operandi su re-gistro e quindi non coinvolgono la cache di dati. La coppia di istruzioni evidenziate coinvolge un long word al medesimo indirizzo e viene eseguita, con indirizzi successivi a distanza di 4, una volta per ci-clo. Vengono pertanto letti/scritti i 10 ($A) longword agli indirizzi: $1000 $1004 $1008 . . . $1024 Essendo completamente associativa, la cache prevede un TAG di blocco con: NumBitTag = NumBitIndirizzo – Log2 NumByteBlocco = NumBitIndirizzo – Log2 32 = NumBitIndi-rizzo – 5 essendo quindi il TAG costituito dall’indirizzo privato dei 5 bit meno significativi. Essendo la cache inizialmente vuota, si verificano i seguenti hit e miss:

N Indirizzo Operazione Tag blocco Hit/miss Commento 1 $1000 Lettura $80 Miss Blocco nuovo (occ. 1) 2 $1000 Scrittura $80 Hit 3 $1004 Lettura $80 Hit 4 $1004 Scrittura $80 Hit 5 $1008 Lettura $80 Hit 6 $1008 Scrittura $80 Hit 7 $100C Lettura $80 Hit 8 $100C Scrittura $80 Hit 9 $1010 Lettura $80 Hit 10 $1010 Scrittura $80 Hit 11 $1014 Lettura $80 Hit 12 $1014 Scrittura $80 Hit 13 $1018 Lettura $80 Hit 14 $1018 Scrittura $80 Hit 15 $101C Lettura $80 Hit 16 $101C Scrittura $80 Hit 17 $1020 Lettura $81 Miss Blocco nuovo (occ. 2) 18 $1020 Scrittura $81 Hit 19 $1024 Lettura $81 Hit 20 $1024 Scrittura $81 Hit

Si noti che essendo il ciclo eseguito un numero di volte non elevato, non si è raggiunto il riempimento della cache e non sono stati necessari rimpiazzi. La percentuale di hit è pari a: ph = (18 / 20) * 100 = 90%

5) Una memoria cache da 16 Kbyte, di tipo set-associativo a 4 vie è costituita da blocchi da 32 byte. Allora la cache ha in tutto Ns set e il byte di indirizzo $123456 ha un TAG pari a TAGS e, se presente in cache, si trova nel set di indice Is (0≤Is≤Ns-1); TAGS e Is vanno indicati in notazio-ne esadecimale.

Ns =128 � |

TAGS = $123 | |

Is = $22 � NumByteCache = NumByteBlocco * NumVie * Ns Ns = NumByteCache / (NumByteBlocco * NumVie) = 16 K / (32 * 4) = 214 / 27 = 27 = 128 NumBitTag = NumBitIndirizzo – NumBitSet – NumBitByteBlocco = NumBitIndirizzo – 7 – 5 TAGS = Indirizzo >> (7+5) = $123456 >> 12 = $123 NumSet = Indirizzo[11..5] = (Indirizzo >> 5) & %1111111 = $91A2 & %1111111 = $22

6) In un sistema PD32 una subroutine riceve 2 parametri d’uscita p1 e p2, passati per riferimento, e alloca una variabile locale L costituita da un vettore di 40 longword. Supponendo che la subroutine utilizzi la tecnica dello stack frame, si completino le tre istruzioni qui sotto ove la prima al-loca la variabile L sul frame e le altre due assegnano al primo parametro d’uscita p1 il valore contenuto in L[5].

ADDL #-160, SP

MOVL +12(FP), R0

MOVL –140(FP), (R0) Facendo riferimento alle fig. 4.29 e 4.30 del testo base, nelle locazioni rispettivamente in posizione rela-tiva al FP +8 e +12 sono collocati i puntatori alle variabili che rappresentano il secondo (p2) e primo parametro (p1) di chiamata, mentre la variabile L di 40 long word (160 byte) occupa le posizioni rela-tive da –160 a –4 estremi compresi. L[i] è collocato ad una distanza i*sizeof(longword)=4*i dall’inizio del vettore e pertanto in posizione relativa –160+4*i rispetto al FP.

7) Un sistema con memoria virtuale a byte singolarmente indirizzabili, utilizza indirizzi logici a 32 bit e ha una lunghezza di pagina pari a 4 Kbyte. Supponendo che la MMU disponga di un TLB (cache completamente associativa) con 32 elementi, ciascuno includente i bit dei campi TAG e DATO, se l’indirizzo fisico è costituito da 18 bit, allora la dimensione del TLB è di NTLB bit.

NTLB = 832 bit NTLB = (NumBitTAG + NumBitDato) * NumElemTLB = = (NumBitTAG + NumBitNumPagFisica) * NumElemTLB NumBitTag = NumBitIndirizzoLogico – Log2 DimPagina = 32 – 12 = 20 bit NumBitNumPagFisica = NumBitIndirizzoFisico - Log2 DimPagina = 18 – 12 = 6 bit NTLB = (20+6) * 32 = 832 bit

8) In un sistema con MMU in cui l’indirizzo logico è da 32 bit e quello fisico da 26 bit, la memoria fisica sia suddivisa in pagine da 4 Kbyte. Allora la dimensione della page table è di NPT bit.

NPT = 14 Mbit Dai dati a disposizione si deve desumere che ciascuno degli elementi della page table contiene il solo numero di pagina fisica. Gli elementi sono pari al numero delle pagine logiche. NPT = NumBitNumPagFisica * NumPagLogiche = = (NumBitIndFisico – Log2 DimPagina) * 2^(NumBitIndLogico – Log2 DimPagina) = = (26-12)*2(32-12) = 14 * 220 bit

9) Un processore è dotato di un pipeline a k=6 stadi e di una memoria cache. Mediamente il numero di accessi in memoria per ogni istruzione è pari a 1,4 e l’hit rate della cache è pari al 90%. Si è rilevato che ogni miss nella cache provoca nel pipeline un inceppamento (ritardo) di 2 stadi. In queste ipotesi il fattore di speedup (T1/Tk), trascurando il transitorio iniziale, è mediamente pari a Sk1

Sk1 = 4.6875

Si supponga inoltre che, a causa dei vari hazard il pipeline subisca mediamente un ulteriore inceppamento di 3 stadi ogni 30 istruzioni. In queste ipotesi il fattore di speedup (T1/Tk), sempre trascurando il transitorio iniziale, è mediamente pari a Sk2

Sk2 = 4.3478

Facendo il calcolo su una successione di N istruzioni a regime, esse producono N*AccessiPerIstruzione accessi in memoria; quelli che si esauriscono in cache sono N*AccessiPerIstruzione*HitRate e non producono inceppamento, mentre la porzione N*AccessiPerIstruzione*(1-HitRate) produce per cia-scun accesso un ritardo di StadiRitardo stadi. Risulta per le N istruzioni: T1 = N * NumStadi * TStadio Tk1 = N*TStadio + N*AccessiPerIstruzione*(1-HitRate)*StadiRitardo*TStadio Sk1 = T1/Tk = NumStadi / (1 + AccessiPerIstruzione*(1-HitRate)*StadiRitardo) = 6 / (1 + 1.4*0.1*2) = = 4.6875 Se si aggiunge il contributo di hazard, pari a N*RateInceppamento stadi, risulta: Tk2 = N*TStadio + N*AccessiPerIstruzione*(1-HitRate)*StadiRitardo*TStadio + + N*RateInceppamento*TStadio Sk2 = T1/Tk2 = = NumStadi / (1 + AccessiPerIstruzione*(1-HitRate)*StadiRitardo + RateInceppamento) = = 6 / (1 + 1.4*0.1*2+3/30) = 4.347826

Cognome ESATTO Nome GIUSTO Matricola B

ARCHITETTURA DEGLI ELABORATORI 1 - Seconda prova intermedia - 23 giugno 2003

1) Un dispositivo DM, gestito ad interrupt, genera periodicamente richieste di interruzioni con periodo Tm; la sua RSI ha durata (complessiva) Rm=70 µs. Un secondo dispositivo DP, più prioritario di DM, ha una RSI di durata (complessiva) Rp=60 µs e può interrompere DM al massimo una volta durante ciascun periodo Tm. Per non perdere dati di DM, il minimo valore di Tm è:

TmMIN=130 µs Poiché è noto che DP può interrompere la RSI di DM al più una sola volta tra due successive richieste di interruzione di quest’ultimo, questa RSI può terminare al più tardi dopo: Tdm = DurataRsiDm+DurataRsiDp dalla prima delle due richieste di DM (DP introduce, con la sua RSI, un ritardo che si aggiunge al tempo necessario all’esecuzione della RSI di DM). Pertanto Tdm è anche il periodo minimo di DM: TmMIN = Tdm = 70+60 = 130 µµµµs

2) Un dispositivo D1 trasferisce, via DMA, blocchi da 700 dati ciascuno. Per comandare il trasferimento di un blocco vengono eseguite dalla CPU 5 istruzioni la cui durata complessiva corrisponde a 20 cicli di bus, la RSI attivata dopo il trasferimento dell’ultimo dato del blocco ha una durata corrispondente a 100 cicli di bus (ciascun ciclo di bus dura 100 ns). Il tempo di CPU complessivamente impegnato per il trasferimento di uno dei blocchi (includendo il ritardo dovuto ad accessi DMA di D1) è al massimo pari a TDMA µs.

TDMA = 82 µs L’impegno della CPU nei confronti di D1 include le istruzioni iniziali, il ritardo complessivo dovuto al fenomeno di cycle stealing durante il trasferimento in DMA, che è al massimo pari al numero di cicli occupati da quel trasferimento (1 ciclo per ogni dato), e l’esecuzione della RSI. TDMA = (CicliIstrIniz + NumDati + CicliRSI) * PeriodoCiclo = (20+700+100)*100 = 82000 ns = 82.0 µµµµs

3) Un ADC può funzionare sia ad interrupt che in DMA: nel primo caso (una richiesta d’interruzione per dato), la RSI ha una durata complessiva di 15 µs, nel secondo caso (una richiesta d’interruzione per blocco di dati), essendo il numero di dati di ogni blocco molto elevato, la durata della RSI è trascurabile. Sapendo che il ciclo di bus ha una durata di 100ns e supponendo di tollerare in entrambi i casi una occupazione massima del tempo di CPU dedicato al dispositivo del 5% (trascurando la RSI del DMA), allora il periodo minimo con cui possono essere trasferiti i dati gesti-ti ad interrupt è TI; quello con cui possono essere trasferiti i dati via DMA è TD.

TI =300 µs

TD =2 µs In caso di gestione ad interrupt, l’occupazione di tempo di CPU è dovuta all’esecuzione di una attiva-zione della routine di servizio ogni periodo del dispositivo. Pertanto risulta: (DurataRsi / TI ) * 100 = PercentualeOccupazione TI = (DurataRSI / PercentualeOccupazione) * 100 = 1500 / 5 = 300 µµµµs In caso di gestione in DMA, l’occupazione ‘equivalente’ è dovuta al cycle stealing. Pertanto risulta: (DurataCiclo / TD ) * 100 = PercentualeOccupazione TD = (DurataCiclo / PercentualeOccupazione) * 100 = 10000 / 5 = 2000 ns = 2 µµµµs

4) Un sistema PD32 è dotato di una instruction cache e di una data cache completamente associative; ciascuna delle due cache contiene 8 blocchi da 16 byte. A data cache vuota, viene eseguito il segmento di codice che segue, caricato in memoria a partire dall’indirizzo $400. Immaginando che la data cache adotti un criterio di rimpiazzo di tipo LRU (Least Recently Used), quando viene eseguita l’istruzione NOP la percentuale di hit sul totale degli accessi alla data cache è pari a ph.

MOVL #$C, R0 MOVL #$1000, R1 LOOP: MOVL (R1), R2

ANDL #$FFE, R2

MOVL R2, (R1)+

SUBL #1, R0

JNZ LOOP

NOP ph=87.5 %

Nella domanda la cache coinvolta è solo quella dei dati. Il codice effettua una lettura dalla memoria nella terza istruzione (la prima del ciclo) e una scrittura nella quinta (la terza del ciclo); le altre istru-zioni contengono dati immediati, letti quindi dall’altra cache durante la fase di fetch, o operandi su re-gistro e quindi non coinvolgono la cache di dati. La coppia di istruzioni evidenziate coinvolge un long word al medesimo indirizzo e viene eseguita, con indirizzi successivi a distanza di 4, una volta per ci-clo. Vengono pertanto letti/scritti i 12 ($C) longword agli indirizzi: $1000 $1004 $1008 . . . $102C Essendo completamente associativa, la cache prevede un TAG di blocco con: NumBitTag = NumBitIndirizzo – Log2 NumByteBlocco = NumBitIndirizzo – Log2 16 = NumBitIndi-rizzo – 4 essendo quindi il TAG costituito dall’indirizzo privato dei 4 bit meno significativi. Essendo la cache inizialmente vuota, si verificano i seguenti hit e miss:

N Indirizzo Operazione Tag blocco Hit/miss Commento 1 $1000 Lettura $100 Miss Blocco nuovo (occ. 1) 2 $1000 Scrittura $100 Hit 3 $1004 Lettura $100 Hit 4 $1004 Scrittura $100 Hit 5 $1008 Lettura $100 Hit 6 $1008 Scrittura $100 Hit 7 $100C Lettura $100 Hit 8 $100C Scrittura $100 Hit 9 $1010 Lettura $101 Miss Blocco nuovo (occ. 2) 10 $1010 Scrittura $101 Hit 11 $1014 Lettura $101 Hit 12 $1014 Scrittura $101 Hit 13 $1018 Lettura $101 Hit 14 $1018 Scrittura $101 Hit 15 $101C Lettura $101 Hit 16 $101C Scrittura $101 Hit 17 $1020 Lettura $102 Miss Blocco nuovo (occ. 3) 18 $1020 Scrittura $102 Hit 19 $1024 Lettura $102 Hit 20 $1024 Scrittura $102 Hit 21 $1028 Lettura $102 Hit 22 $1028 Scrittura $102 Hit 23 $102C Lettura $102 Hit 24 $102C Scrittura $102 Hit

Si noti che essendo il ciclo eseguito un numero di volte non elevato, non si è raggiunto il riempimento della cache e non sono stati necessari rimpiazzi. La percentuale di hit è pari a: ph = (21 / 24) * 100 = 87.5 %

5) Una memoria cache da 32 Kbyte, di tipo set-associativo a 8 vie è costituita da blocchi da 32 byte. Allora la cache ha in tutto Ns set e il byte di indirizzo $ABC01F ha un TAG pari a TAGS e, se presente in cache, si trova nel set di indice Is (0≤Is≤Ns-1); TAGS e Is vanno indicati in nota-zione esadecimale.

Ns =128 � |

TAGS =$ABC | |

Is =$0� NumByteCache = NumByteBlocco * NumVie * Ns Ns = NumByteCache / (NumByteBlocco * NumVie) = 32 K / (32 * 8) = 215 / 28 = 27 = 128 NumBitTag = NumBitIndirizzo – NumBitSet – NumBitByteBlocco = NumBitIndirizzo – 7 – 5 TAGS = Indirizzo >> (7+5) = $ABC01F >> 12 = $ABC NumSet = Indirizzo[11..5] = (Indirizzo >> 5) & %1111111 = $55E00 & %1111111 = $0

6) In un sistema PD32 una subroutine riceve 2 parametri d’uscita p1 e p2, passati per riferimento, e alloca una variabile locale L costituita da un vettore di 30 longword. Supponendo che la subroutine utilizzi la tecnica dello stack frame, si completino le tre istruzioni qui sotto ove la prima al-loca la variabile L sul frame e le altre due assegnano al secondo parametro d’uscita p2 il valore contenuto in L[25].

ADDL #-120, SP

MOVL +8(FP), R1

MOVL –20(FP), (R1) Facendo riferimento alle fig. 4.29 e 4.30 del testo base, nelle locazioni rispettivamente in posizione rela-tiva al FP +8 e +12 sono collocati i puntatori alle variabili che rappresentano il secondo (p2) e primo parametro (p1) di chiamata, mentre la variabile L di 30 long word (120 byte) occupa le posizioni rela-tive da –120 a –4 estremi compresi. L[i] è collocato ad una distanza i*sizeof(longword)=4*i dall’inizio del vettore e pertanto in posizione relativa –120+4*i rispetto al FP.

7) Un sistema con memoria virtuale a byte singolarmente indirizzabili, utilizza indirizzi logici a 48 bit e ha una lunghezza di pagina pari a 64 Kbyte. Supponendo che la MMU disponga di un TLB (cache completamente associativa) con 64 elementi, ciascuno includente i bit dei campi TAG e DATO, se l’indirizzo fisico è costituito da 28 bit, allora la dimensione del TLB è di NTLB bit.

NTLB =2816 bit NTLB = (NumBitTAG + NumBitDato) * NumElemTLB = = (NumBitTAG + NumBitNumPagFisica) * NumElemTLB

NumBitTag = NumBitIndirizzoLogico – Log2 DimPagina = 48 – 16 = 32 bit NumBitNumPagFisica = NumBitIndirizzoFisico - Log2 DimPagina = 28 – 16 = 12 bit NTLB = (32+12) * 64 = 2816 bit

8) In un sistema con MMU in cui l’indirizzo logico è da 40 bit e quello fisico da 32 bit, la memoria fisica sia suddivisa in pagine da 1 Mbyte. Allo-ra la dimensione della page table è di NPT bit.

NPT =12M bit Dai dati a disposizione si deve desumere che ciascuno degli elementi della page table contiene il solo numero di pagina fisica. Gli elementi sono pari al numero delle pagine logiche. NPT = NumBitNumPagFisica * NumPagLogiche = = (NumBitIndFisico – Log2 DimPagina) * 2^(NumBitIndLogico – Log2 DimPagina) = = (32-20)*2(40-20) = 12 * 220 bit

9) Un processore è dotato di un pipeline a 8 stadi e di una memoria cache. Mediamente il numero di accessi in memoria per ogni istruzione è pari a 1,9 e l’hit rate della cache è pari al 95%. Si è rilevato che ogni miss nella cache provoca nel pipeline un inceppamento (ritardo) di 3 stadi. In queste ipotesi il fattore di speedup (T1/Tk), trascurando il transitorio iniziale, è mediamente pari a Sk1

Sk1 =6.225681

Si supponga inoltre che, a causa dei vari hazard il pipeline subisca mediamente un ulteriore inceppamento di 4 stadi ogni 20 istruzioni. In queste ipotesi il fattore di speedup (T1/Tk), sempre trascurando il transitorio iniziale, è mediamente pari a Sk2

Sk2 =5.387205

Facendo il calcolo su una successione di N istruzioni a regime, esse producono N*AccessiPerIstruzione accessi in memoria; quelli che si esauriscono in cache sono N*AccessiPerIstruzione*HitRate e non producono inceppamento, mentre la porzione N*AccessiPerIstruzione*(1-HitRate) produce per cia-scun accesso un ritardo di StadiRitardo stadi. Risulta per le N istruzioni: T1 = N * NumStadi * TStadio Tk1 = N*TStadio + N*AccessiPerIstruzione*(1-HitRate)*StadiRitardo*TStadio Sk1 = T1/Tk = NumStadi / (1 + AccessiPerIstruzione*(1-HitRate)*StadiRitardo) = = 8 / (1 + 1.9*0.05*3) = 6.225681 Se si aggiunge il contributo di hazard, pari a N*RateInceppamento stadi, risulta: Tk2 = N*TStadio + N*AccessiPerIstruzione*(1-HitRate)*StadiRitardo*TStadio + + N*RateInceppamento*TStadio Sk2 = T1/Tk2 = = NumStadi / (1 + AccessiPerIstruzione*(1-HitRate)*StadiRitardo + RateInceppamento) = = 8 / (1 + 1.9*0.05*3+4/20) = 5.387205

Cognome ESATTO Nome GIUSTO Matricola C

ARCHITETTURA DEGLI ELABORATORI 1 - Seconda prova intermedia - 23 giugno 2003

1) Un dispositivo DM, gestito ad interrupt, genera periodicamente richieste di interruzioni con periodo Tm; la sua RSI ha durata (complessiva) Rm=120 µs. Un secondo dispositivo DP, più prioritario di DM, ha una RSI di durata (complessiva) Rp=40 µs e può interrompere DM al massi-mo una volta durante ciascun periodo Tm. Per non perdere dati di DM, il minimo valore di Tm è:

TmMIN=160 µs Poiché è noto che DP può interrompere la RSI di DM al più una sola volta tra due successive richieste di interruzione di quest’ultimo, questa RSI può terminare al più tardi dopo: Tdm = DurataRsiDm+DurataRsiDp dalla prima delle due richieste di DM (DP introduce, con la sua RSI, un ritardo che si aggiunge al tempo necessario all’esecuzione della RSI di DM). Pertanto Tdm è anche il periodo minimo di DM: TmMIN = Tdm = 120+40 = 160 µµµµs

2) Un dispositivo D1 trasferisce, via DMA, blocchi da 500 dati ciascuno. Per comandare il trasferimento di un blocco vengono eseguite dalla CPU 7 istruzioni la cui durata complessiva corrisponde a 30 cicli di bus, la RSI attivata dopo il trasferimento dell’ultimo dato del blocco ha una dura-ta corrispondente a 70 cicli di bus (ciascun ciclo di bus dura 90 ns). Il tempo di CPU complessivamente impegnato per il trasferimento di uno dei blocchi (includendo il ritardo dovuto ad accessi DMA di D1) è al massimo pari a TDMA µs.

TDMA = 54 µs L’impegno della CPU nei confronti di D1 include le istruzioni iniziali, il ritardo complessivo dovuto al fenomeno di cycle stealing durante il trasferimento in DMA, che è al massimo pari al numero di cicli occupati da quel trasferimento (1 ciclo per ogni dato), e l’esecuzione della RSI. TDMA = (CicliIstrIniz + NumDati + CicliRSI) * PeriodoCiclo = (30+500+70)*90 = 54000 ns = 54.0 µµµµs

3) Un ADC può funzionare sia ad interrupt che in DMA: nel primo caso (una richiesta d’interruzione per dato), la RSI ha una durata complessiva di 13 µs, nel secondo caso (una richiesta d’interruzione per blocco di dati), essendo il numero di dati di ogni blocco molto elevato, la durata del-la RSI è trascurabile. Sapendo che il ciclo di bus ha una durata di 140ns e supponendo di tollerare in entrambi i casi una occupazione massima del tempo di CPU dedicato al dispositivo del 4% (trascurando la RSI del DMA), allora il periodo minimo con cui possono essere trasferiti i dati gestiti ad interrupt è TI; quello con cui possono essere trasferiti i dati via DMA è TD.

TI =325 µs

TD =3.5 µs In caso di gestione ad interrupt, l’occupazione di tempo di CPU è dovuta all’esecuzione di una attiva-zione della routine di servizio ogni periodo del dispositivo. Pertanto risulta: (DurataRsi / TI ) * 100 = PercentualeOccupazione TI = (DurataRSI / PercentualeOccupazione) * 100 = 1300 / 4 = 325 µµµµs In caso di gestione in DMA, l’occupazione ‘equivalente’ è dovuta al cycle stealing. Pertanto risulta: (DurataCiclo / TD ) * 100 = PercentualeOccupazione TD = (DurataCiclo / PercentualeOccupazione) * 100 = 14000 / 4 = 3500 ns = 3.5 µµµµs

4) Un sistema PD32 è dotato di una instruction cache e di una data cache completamente associative; ciascuna delle due cache contiene 16 bloc-chi da 8 byte. A data cache vuota, viene eseguito il segmento di codice che segue, caricato in memoria a partire dall’indirizzo $400. Immagi-nando che la data cache adotti un criterio di rimpiazzo di tipo LRU (Least Recently Used), quando viene eseguita l’istruzione NOP la percentua-le di hit sul totale degli accessi alla data cache è pari a ph.

MOVL #$8, R0 MOVL #$1000, R1 LOOP: MOVL (R1), R2

ANDL #$FFE, R2

MOVL R2, (R1)+

SUBL #1, R0

JNZ LOOP

NOP ph=75 %

Nella domanda la cache coinvolta è solo quella dei dati. Il codice effettua una lettura dalla memoria nella terza istruzione (la prima del ciclo) e una scrittura nella quinta (la terza del ciclo); le altre istru-zioni contengono dati immediati, letti quindi dall’altra cache durante la fase di fetch, o operandi su re-gistro e quindi non coinvolgono la cache di dati. La coppia di istruzioni evidenziate coinvolge un long word al medesimo indirizzo e viene eseguita, con indirizzi successivi a distanza di 4, una volta per ci-clo. Vengono pertanto letti/scritti gli 8 ($8) longword agli indirizzi: $1000 $1004 $1008 . . . $101C Essendo completamente associativa, la cache prevede un TAG di blocco con: NumBitTag = NumBitIndirizzo – Log2 NumByteBlocco = NumBitIndirizzo – Log2 8 = NumBitIndi-rizzo – 3 essendo quindi il TAG costituito dall’indirizzo privato dei 3 bit meno significativi. Essendo la cache inizialmente vuota, si verificano i seguenti hit e miss:

N Indirizzo Operazione Tag blocco Hit/miss Commento 1 $1000 Lettura $200 Miss Blocco nuovo (occ. 1) 2 $1000 Scrittura $200 Hit 3 $1004 Lettura $200 Hit 4 $1004 Scrittura $200 Hit 5 $1008 Lettura $201 Miss Blocco nuovo (occ. 2) 6 $1008 Scrittura $201 Hit 7 $100C Lettura $201 Hit 8 $100C Scrittura $201 Hit 9 $1010 Lettura $202 Miss Blocco nuovo (occ. 3) 10 $1010 Scrittura $202 Hit 11 $1014 Lettura $202 Hit 12 $1014 Scrittura $202 Hit 13 $1018 Lettura $203 Miss Blocco nuovo (occ. 4) 14 $1018 Scrittura $203 Hit 15 $101C Lettura $203 Hit 16 $101C Scrittura $203 Hit

Si noti che essendo il ciclo eseguito un numero di volte non elevato, non si è raggiunto il riempimento della cache e non sono stati necessari rimpiazzi. La percentuale di hit è pari a: ph = (12 / 16) * 100 = 75%

5) Una memoria cache da 16 Kbyte, di tipo set-associativo a 4 vie è costituita da blocchi da 8 byte. Allora la cache ha in tutto Ns set e il byte di indirizzo $23507A ha un TAG pari a TAGS e, se presente in cache, si trova nel set di indice Is (0≤Is≤Ns-1); TAGS e Is vanno indicati in nota-zione esadecimale.

Ns =512 � |

TAGS =$235 | |

Is =$F � NumByteCache = NumByteBlocco * NumVie * Ns Ns = NumByteCache / (NumByteBlocco * NumVie) = 16 K / (8 * 4) = 214 / 25 = 29 = 512 NumBitTag = NumBitIndirizzo – NumBitSet – NumBitByteBlocco = NumBitIndirizzo – 9 – 3 TAGS = Indirizzo >> (9+3) = $23507A >> 12 = $235 NumSet = Indirizzo[11..3] = (Indirizzo >> 3) & %111111111 = $46A0F & %111111111 = $F

6) In un sistema PD32 una subroutine riceve 2 parametri d’uscita p1 e p2, passati per riferimento, e alloca una variabile locale L costituita da un vettore di 15 longword. Supponendo che la subroutine utilizzi la tecnica dello stack frame, si completino le tre istruzioni qui sotto ove la prima alloca la variabile L sul frame e le altre due assegnano al primo parametro d’uscita p1 il valore contenuto in L[1].

ADDL #-60, SP

MOVL +12(FP), R2

MOVL –56(FP), (R2) Facendo riferimento alle fig. 4.29 e 4.30 del testo base, nelle locazioni rispettivamente in posizione rela-tiva al FP +8 e +12 sono collocati i puntatori alle variabili che rappresentano il secondo (p2) e primo parametro (p1) di chiamata, mentre la variabile L di 15 long word (60 byte) occupa le posizioni relati-ve da –60 a –4 estremi compresi. L[i] è collocato ad una distanza i*sizeof(longword)=4*i dall’inizio del vettore e pertanto in posizione relativa –60+4*i rispetto al FP.

7) Un sistema con memoria virtuale a byte singolarmente indirizzabili, utilizza indirizzi logici a 32 bit e ha una lunghezza di pagina pari a 16 Kbyte. Supponendo che la MMU disponga di un TLB (cache completamente associativa) con 32 elementi, ciascuno includente i bit dei campi TAG e DATO, se l’indirizzo fisico è costituito da 24 bit, allora la dimensione del TLB è di NTLB bit.

NTLB =896 bit NTLB = (NumBitTAG + NumBitDato) * NumElemTLB = = (NumBitTAG + NumBitNumPagFisica) * NumElemTLB NumBitTag = NumBitIndirizzoLogico – Log2 DimPagina = 32 – 14 = 18 bit NumBitNumPagFisica = NumBitIndirizzoFisico - Log2 DimPagina = 24 – 14 = 10 bit NTLB = (18+10) * 32 = 896 bit

8) In un sistema con MMU in cui l’indirizzo logico è da 32 bit e quello fisico da 22 bit, la memoria fisica sia suddivisa in pagine da 16 Kbyte. Al-lora la dimensione della page table è di NPT bit.

NPT =2M bit Dai dati a disposizione si deve desumere che ciascuno degli elementi della page table contiene il solo numero di pagina fisica. Gli elementi sono pari al numero delle pagine logiche.

NPT = NumBitNumPagFisica * NumPagLogiche = = (NumBitIndFisico – Log2 DimPagina) * 2^(NumBitIndLogico – Log2 DimPagina) = = (22-14)*2(32-14) = 8 * 218 = 2 * 220 bit

9) Un processore è dotato di un pipeline a k=5 stadi e di una memoria cache. Mediamente il numero di accessi in memoria per ogni istruzione è pari a 1,2 e l’hit rate della cache è pari all’88%. Si è rilevato che ogni miss nella cache provoca nel pipeline un inceppamento (ritardo) di 2 sta-di. In queste ipotesi il fattore di speedup (T1/Tk), trascurando il transitorio iniziale, è mediamente pari a Sk1

Sk1 =3.881988

Si supponga inoltre che, a causa dei vari hazard il pipeline subisca mediamente un ulteriore inceppamento di 1 stadio ogni 8 istruzioni. In queste ipotesi il fattore di speedup (T1/Tk), sempre trascurando il transitorio iniziale, è mediamente pari a Sk2

Sk2 =3.53857

Facendo il calcolo su una successione di N istruzioni a regime, esse producono N*AccessiPerIstruzione accessi in memoria; quelli che si esauriscono in cache sono N*AccessiPerIstruzione*HitRate e non producono inceppamento, mentre la porzione N*AccessiPerIstruzione*(1-HitRate) produce per cia-scun accesso un ritardo di StadiRitardo stadi. Risulta per le N istruzioni: T1 = N * NumStadi * TStadio Tk1 = N*TStadio + N*AccessiPerIstruzione*(1-HitRate)*StadiRitardo*TStadio Sk1 = T1/Tk = NumStadi / (1 + AccessiPerIstruzione*(1-HitRate)*StadiRitardo) = = 5 / (1 + 1.2*0.12*2) = 3.881988 Se si aggiunge il contributo di hazard, pari a N*RateInceppamento stadi, risulta: Tk2 = N*TStadio + N*AccessiPerIstruzione*(1-HitRate)*StadiRitardo*TStadio + + N*RateInceppamento*TStadio Sk2 = T1/Tk2 = = NumStadi / (1 + AccessiPerIstruzione*(1-HitRate)*StadiRitardo + RateInceppamento) = = 5 / (1 + 1.2*0.12*2+1/8) = 3.53857

Cognome ESATTO Nome GIUSTO Matricola D

ARCHITETTURA DEGLI ELABORATORI 1 - Seconda prova intermedia - 23 giugno 2003

1) Un dispositivo DM, gestito ad interrupt, genera periodicamente richieste di interruzioni con periodo Tm; la sua RSI ha durata (complessiva) Rm=90 µs. Un secondo dispositivo DP, più prioritario di DM, ha una RSI di durata (complessiva) Rp=100 µs e può interrompere DM al massi-mo una volta durante ciascun periodo Tm. Per non perdere dati di DM, il minimo valore di Tm è:

TmMIN=190 µs Poiché è noto che DP può interrompere la RSI di DM al più una sola volta tra due successive richieste di interruzione di quest’ultimo, questa RSI può terminare al più tardi dopo: Tdm = DurataRsiDm+DurataRsiDp dalla prima delle due richieste di DM (DP introduce, con la sua RSI, un ritardo che si aggiunge al tempo necessario all’esecuzione della RSI di DM). Pertanto Tdm è anche il periodo minimo di DM: TmMIN = Tdm = 90+100 = 190 µµµµs

2) Un dispositivo D1 trasferisce, via DMA, blocchi da 800 dati ciascuno. Per comandare il trasferimento di un blocco vengono eseguite dalla CPU 5 istruzioni la cui durata complessiva corrisponde a 15 cicli di bus, la RSI attivata dopo il trasferimento dell’ultimo dato del blocco ha una dura-ta corrispondente a 85 cicli di bus (ciascun ciclo di bus dura 120 ns). Il tempo di CPU complessivamente impegnato per il trasferimento di uno dei blocchi (includendo il ritardo dovuto ad accessi DMA di D1) è al massimo pari a TDMA µs.

TDMA = 108 µs L’impegno della CPU nei confronti di D1 include le istruzioni iniziali, il ritardo complessivo dovuto al fenomeno di cycle stealing durante il trasferimento in DMA, che è al massimo pari al numero di cicli occupati da quel trasferimento (1 ciclo per ogni dato), e l’esecuzione della RSI. TDMA = (CicliIstrIniz + NumDati + CicliRSI) * PeriodoCiclo = (15+800+85)*120 = 108000 ns = 108.0 µµµµs

3) Un ADC può funzionare sia ad interrupt che in DMA: nel primo caso (una richiesta d’interruzione per dato), la RSI ha una durata complessiva di 12 µs, nel secondo caso (una richiesta d’interruzione per blocco di dati), essendo il numero di dati di ogni blocco molto elevato, la durata del-la RSI è trascurabile. Sapendo che il ciclo di bus ha una durata di 150ns e supponendo di tollerare in entrambi i casi una occupazione massima del tempo di CPU dedicato al dispositivo del 3% (trascurando la RSI del DMA), allora il periodo minimo con cui possono essere trasferiti i dati gestiti ad interrupt è TI; quello con cui possono essere trasferiti i dati via DMA è TD.

TI =400 µs

TD =5 µs In caso di gestione ad interrupt, l’occupazione di tempo di CPU è dovuta all’esecuzione di una attiva-zione della routine di servizio ogni periodo del dispositivo. Pertanto risulta: (DurataRsi / TI ) * 100 = PercentualeOccupazione TI = (DurataRSI / PercentualeOccupazione) * 100 = 1200 / 3 = 400 µµµµs In caso di gestione in DMA, l’occupazione ‘equivalente’ è dovuta al cycle stealing. Pertanto risulta: (DurataCiclo / TD ) * 100 = PercentualeOccupazione TD = (DurataCiclo / PercentualeOccupazione) * 100 = 15000 / 3 = 5000 ns = 5 µµµµs

4) Un sistema PD32 è dotato di una instruction cache e di una data cache completamente associative; ciascuna delle due cache contiene 32 bloc-chi da 16 byte. A data cache vuota, viene eseguito il segmento di codice che segue, caricato in memoria a partire dall’indirizzo $400. Immagi-nando che la data cache adotti un criterio di rimpiazzo di tipo LRU (Least Recently Used), quando viene eseguita l’istruzione NOP la percentua-le di hit sul totale degli accessi alla data cache è pari a ph.

MOVL #$F, R0 MOVL #$1000, R1 LOOP: MOVL (R1), R2

ANDL #$FFE, R2

MOVL R2, (R1)+

SUBL #1, R0

JNZ LOOP

NOP ph=86.667 %

Nella domanda la cache coinvolta è solo quella dei dati. Il codice effettua una lettura dalla memoria nella terza istruzione (la prima del ciclo) e una scrittura nella quinta (la terza del ciclo); le altre istru-zioni contengono dati immediati, letti quindi dall’altra cache durante la fase di fetch, o operandi su re-gistro e quindi non coinvolgono la cache di dati. La coppia di istruzioni evidenziate coinvolge un long word al medesimo indirizzo e viene eseguita, con indirizzi successivi a distanza di 4, una volta per ci-clo. Vengono pertanto letti/scritti i 15 ($F) longword agli indirizzi: $1000 $1004 $1008 . . . $1038 Essendo completamente associativa, la cache prevede un TAG di blocco con: NumBitTag = NumBitIndirizzo – Log2 NumByteBlocco = NumBitIndirizzo – Log2 16 = NumBitIndi-rizzo – 4 essendo quindi il TAG costituito dall’indirizzo privato dei 4 bit meno significativi. Essendo la cache inizialmente vuota, si verificano i seguenti hit e miss:

N Indirizzo Operazione Tag blocco Hit/miss Commento 1 $1000 Lettura $100 Miss Blocco nuovo (occ. 1) 2 $1000 Scrittura $100 Hit 3 $1004 Lettura $100 Hit 4 $1004 Scrittura $100 Hit 5 $1008 Lettura $100 Hit 6 $1008 Scrittura $100 Hit 7 $100C Lettura $100 Hit 8 $100C Scrittura $100 Hit 9 $1010 Lettura $101 Miss Blocco nuovo (occ. 2) 10 $1010 Scrittura $101 Hit 11 $1014 Lettura $101 Hit 12 $1014 Scrittura $101 Hit 13 $1018 Lettura $101 Hit 14 $1018 Scrittura $101 Hit 15 $101C Lettura $101 Hit 16 $101C Scrittura $101 Hit 17 $1020 Lettura $102 Miss Blocco nuovo (occ. 3) 18 $1020 Scrittura $102 Hit 19 $1024 Lettura $102 Hit 20 $1024 Scrittura $102 Hit 21 $1028 Lettura $102 Hit 22 $1028 Scrittura $102 Hit 23 $102C Lettura $102 Hit 24 $102C Scrittura $102 Hit 25 $1030 Lettura $103 Miss Blocco nuovo (occ. 4) 26 $1030 Scrittura $103 Hit 27 $1034 Lettura $103 Hit 28 $1034 Scrittura $103 Hit 29 $1038 Lettura $103 Hit 30 $1034 Scrittura $103 Hit

Si noti che essendo il ciclo eseguito un numero di volte non elevato, non si è raggiunto il riempimento della cache e non sono stati necessari rimpiazzi. La percentuale di hit è pari a: ph = (26 / 30) * 100 = 86.667%

5) Una memoria cache da 64 Kbyte, di tipo set-associativo a 16 vie è costituita da blocchi da 128 byte. Allora la cache ha in tutto Ns set e il byte di indirizzo $110963 ha un TAG pari a TAGS e, se presente in cache, si trova nel set di indice Is (0≤Is≤Ns-1); TAGS e Is vanno indicati in nota-zione esadecimale.

Ns =32 � |

TAGS =$110 | |

Is =$12 � NumByteCache = NumByteBlocco * NumVie * Ns Ns = NumByteCache / (NumByteBlocco * NumVie) = 64 K / (128 * 16) = 216 / 211 = 25 = 32 NumBitTag = NumBitIndirizzo – NumBitSet – NumBitByteBlocco = NumBitIndirizzo – 5 – 7 TAGS = Indirizzo >> (5+7) = $110963 >> 12 = $110 NumSet = Indirizzo[11..7] = (Indirizzo >> 7) & %11111 = $2212 & %1111111 = $12

6) In un sistema PD32 una subroutine riceve 2 parametri d’uscita p1 e p2, passati per riferimento, e alloca una variabile locale L costituita da un vettore di 20 longword. Supponendo che la subroutine utilizzi la tecnica dello stack frame, si completino le tre istruzioni qui sotto ove la prima alloca la variabile L sul frame e le altre due assegnano al secondo parametro d’uscita p2 il valore contenuto in L[19].

ADDL #-80, SP

MOVL +8(FP), R3

MOVL –4(FP), (R3) Facendo riferimento alle fig. 4.29 e 4.30 del testo base, nelle locazioni rispettivamente in posizione rela-tiva al FP +8 e +12 sono collocati i puntatori alle variabili che rappresentano il secondo (p2) e primo parametro (p1) di chiamata, mentre la variabile L di 20 long word (80 byte) occupa le posizioni relati-ve da –80 a –4 estremi compresi. L[i] è collocato ad una distanza i*sizeof(longword)=4*i dall’inizio del vettore e pertanto in posizione relativa –80+4*i rispetto al FP.

7) Un sistema con memoria virtuale a byte singolarmente indirizzabili, utilizza indirizzi logici a 40 bit e ha una lunghezza di pagina pari a 32 Kbyte. Supponendo che la MMU disponga di un TLB (cache completamente associativa) con 16 elementi, ciascuno includente i bit dei campi TAG e DATO, se l’indirizzo fisico è costituito da 32 bit, allora la dimensione del TLB è di NTLB bit.

NTLB =672 bit NTLB = (NumBitTAG + NumBitDato) * NumElemTLB = = (NumBitTAG + NumBitNumPagFisica) * NumElemTLB NumBitTag = NumBitIndirizzoLogico – Log2 DimPagina = 40 – 15 = 25 bit NumBitNumPagFisica = NumBitIndirizzoFisico - Log2 DimPagina = 32 – 15 = 17 bit NTLB = (25+17) * 16 = 672 bit

8) In un sistema con MMU in cui l’indirizzo logico è da 36 bit e quello fisico da 32 bit, la memoria fisica sia suddivisa in pagine da 64 Kbyte. Al-lora la dimensione della page table è di NPT bit.

NPT =16M bit Dai dati a disposizione si deve desumere che ciascuno degli elementi della page table contiene il solo numero di pagina fisica. Gli elementi sono pari al numero delle pagine logiche. NPT = NumBitNumPagFisica * NumPagLogiche = = (NumBitIndFisico – Log2 DimPagina) * 2^(NumBitIndLogico – Log2 DimPagina) = = (32-16)*2(36-16) = 16 * 220 bit

9) Un processore è dotato di un pipeline a k=9 stadi e di una memoria cache. Mediamente il numero di accessi in memoria per ogni istruzione è pari a 1,3 e l’hit rate della cache è pari al 93%. Si è rilevato che ogni miss nella cache provoca nel pipeline un inceppamento (ritardo) di 4 stadi. In queste ipotesi il fattore di speedup (T1/Tk), trascurando il transitorio iniziale, è mediamente pari a Sk1

Sk1 =6.59824

Si supponga inoltre che, a causa dei vari hazard il pipeline subisca mediamente un ulteriore inceppamento di 3 stadi ogni 24 istruzioni. In queste ipotesi il fattore di speedup (T1/Tk), sempre trascurando il transitorio iniziale, è mediamente pari a Sk2

Sk2 =6.044325

Facendo il calcolo su una successione di N istruzioni a regime, esse producono N*AccessiPerIstruzione accessi in memoria; quelli che si esauriscono in cache sono N*AccessiPerIstruzione*HitRate e non producono inceppamento, mentre la porzione N*AccessiPerIstruzione*(1-HitRate) produce per cia-scun accesso un ritardo di StadiRitardo stadi. Risulta per le N istruzioni: T1 = N * NumStadi * TStadio Tk1 = N*TStadio + N*AccessiPerIstruzione*(1-HitRate)*StadiRitardo*TStadio Sk1 = T1/Tk = NumStadi / (1 + AccessiPerIstruzione*(1-HitRate)*StadiRitardo) = = 9 / (1 + 1.3*0.07*4) = 6.59824 Se si aggiunge il contributo di hazard, pari a N*RateInceppamento stadi, risulta: Tk2 = N*TStadio + N*AccessiPerIstruzione*(1-HitRate)*StadiRitardo*TStadio + + N*RateInceppamento*TStadio Sk2 = T1/Tk2 = = NumStadi / (1 + AccessiPerIstruzione*(1-HitRate)*StadiRitardo + RateInceppamento) = = 9 / (1 + 1.3*0.07*4+3/24) = 6.044325