AA11_12_DIARIO < Architetture2/MZ

<H1>Architettura degli Elaboratori a.a. 2011-2012 <SMALL>(canale M-Z)</SMALL></H1>


<H2>Diario delle lezioni e delle esercitazioni</H2>

<DIV style="margin-left:5%; margin-right:5%">
<DIV ALIGN="justify">
<B>Luned&igrave; 5 marzo 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Informazioni sul corso e brevissima panoramica dei contenuti del corso.
Cenni sulla storia dei computer: dall'ENIAC al Pentium,
passando per il <b>MIPS</b>. Il concetto di <em>stored program</em>.
L'architettura di un computer e i suoi aspetti: <em>ISA</em> (<em>Instruction Set Architecture</em>), 
<em>organizzazione</em> e <em>hardware</em>.
Caratteristiche che distinguono le architetture.
<ul>
<li>Tipo della memoria interna: <em>accumulator</em>, <em>stack</em>, 
<em>extended accumulator</em> (o <em>special-purpose registers</em>), 
<em>general-purpose registers</em> (<em>GPR</em>). 
</li>
<li>Tipo di accesso alla memoria: <em>register-memory</em> e 
<em>load-store</em>.
</li>
<li>Complessit&agrave; dell'insieme delle istruzioni: 
<em>CISC</em> (<em>Complex Instruction Set Computer</em>) e <em>RISC</em> 
(<em>Reduced Instruction Set Computer</em>).</li>
</ul>
Classificazione di varie architetture della storia e del presente 
in base a queste caratteristiche. Discussione delle differenze tra CISC e RISC,
inquadramento storico di MIPS.
</DIV>
<br>
<DIV ALIGN="justify">
<B>Venerd&igrave; 9 marzo 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Vista dall'alto di un computer (architettura di von Neumann).
Le propriet&agrave; che caratterizzano una architettura RISC e
le tipologie delle istruzioni: istruzioni ALU, trasferimento dati
e salti condizionati (<em>branches</em>) e non (<em>jumps</em>).
I registri e le prime istruzioni MIPS: <code>add</code>,
<code>addi</code>, <code>sub</code>. Rappresentazione in memoria
delle istruzioni. Formati R, I e J. Istruzioni di branch e jump:
<code>beq</code>, <code>bne</code>, <code>bgez</code>, <code>bgtz</code>,
<code>blez</code>, <code>bltz</code>, <code>j</code>. Alcune <em>pseudo-istruzioni</em> 
del linguaggio assembly del MIPS: <code>li</code>, <code>move</code>,
<code>bge</code>, <code>bgt</code>,
<code>ble</code>, <code>blt</code>. Esempi: programma
che calcola il massimo di tre numeri e programma che calcola 
il k-esimo numero di Fibonacci (algoritmo iterativo).
<BR>
<B>Esercizio</B> &nbsp;&nbsp; Scrivere un programma che ordina,
in senso cresente, i numeri in <code>$s0</code>,
<code>$s1</code>, <code>$s2</code>. Al termine dell'esecuzione 
in <code>$s0</code>, <code>$s1</code>, <code>$s2</code> ci devono
essere i tre numeri ordinati.
</DIV>
<br>
<DIV ALIGN="justify">
<B>Luned&igrave; 12 marzo 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzione dell'esercizio. Le istruzioni <code>slt</code>,
<code>slti</code> e cenni sull'implementazione delle
pseudo-istruzioni di branch. Le istruzioni logiche:
<code>and</code>, <code>andi</code>, <code>or</code>, <code>ori</code>, 
<code>xor</code>, <code>xori</code>, <code>nor</code> (la pseudo-istruzione 
<code>not</code>). Le istruzioni di shift: <code>sll</code>, <code>srl</code>, 
<code>sllv</code>, <code>srlv</code>. Esempio: conteggio dei bit 1 
in una word (registro). Istruzioni per il trasferimento dei dati: 
<code>lw</code>, <code>sw</code>. Convenzioni MIPS per l'uso
della memoria: <em>Segmento Testo</em>, <em>Segmento Dati</em>, 
<em>Heap</em> e <em>Stack</em>. Alcune direttive dell'assembler:
<code>.data</code>, <code>.word</code>, <code>.text</code>.
Esempio: somma dei valori di un array nel Segmento Dati.
<BR>
<B>Esercizio</B> &nbsp;&nbsp; Scrivere un programma che,
dato un array nel Segmento Dati, incrementa di 1 tutti gli
elementi dell'array.
</div>
<br>
<DIV ALIGN="justify">
<B>Venerd&igrave; 16 marzo 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercitazioni (David Benedetti): [[%ATTACHURL%/AssemblerEsercizi16_03_2012.zip][Esercizi di assembly svolti]].
</div>
<br>
<DIV ALIGN="justify">
<B>Luned&igrave; 19 marzo 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzioni esercizio (12/3/2012): tramite indici e tramite puntatori.
Procedure e il supporto per la loro chiamata: istruzioni <code>jal</code>, 
<code>jr</code> e il registro <code>$ra</code>. Registri per i 
parametri <code>$a0-$a3</code> e per i valori ritornati <code>$v0,$v1</code>. 
Esempio: procedura per calcolare il k-esimo numero di Fibonacci 
(iterativamente). Convenzioni relative all'uso dei registri nelle procedure e
al preservare il loro valore. Lo <em>Stack</em> e il registro <code>$sp</code>.
Esempio di procedura che chiama un'altra procedura: procedura che ordina un
array tramite selection-sort. Cenni sulla implementazione di procedure 
ricorsive.
<BR>
<B>Esercizio</B> &nbsp;&nbsp; 
Scrivere una procedura che calcola il fattoriale in modo 
ricorsivo.
</div>
<br>
<DIV ALIGN="justify">
<B>Venerd&igrave; 23 marzo 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzione esercizio: istruzione <code>mul</code>. 
Procedura ricorsiva che calcola il k-esimo numero di Fibonacci.
Aspetti che influenzano le prestazioni di un computer: software e hardware.
Frequenza di clock e CPI (<em>Clock cycles Per Instruction</em>).
Implementazione ad un ciclo di clock dell'ISA di MIPS: metodologia di
clocking, il datapath, il caricamento dell'istruzione e
l'incremento del PC, esecuzione delle istruzioni di tipo R (<code>add</code>,
<code>sub</code>, ecc.); implementazione del blocco dei registri.
<BR>
<B>Esercizio</B> &nbsp;&nbsp; 
Implementare una procedura per la ricerca binaria ricorsiva:
<code>a0</code>: puntatore al primo elemento;
<code>a1</code>: puntatore all'ultimo elemento; <code>a2</code>: valore
cercato; <code>v0</code>: ritorna il puntatore all'elemento con il valore 
cercato o <code>0</code> se non esiste. 
</div>
<br>
<DIV ALIGN="justify">
<B>Luned&igrave; 26 marzo 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzione esercizio. Implementazione ad un ciclo di clock dell'ISA di MIPS:
le istruzioni di accesso alla memoria (<code>lw</code>, <code>sw</code>),
porzione dell'implementazione per l'esecuzione sia delle istruzioni di tipo R 
che di quelle che accedono alla memoria.
</div>
<br>
<DIV ALIGN="justify">
<B>Venerd&igrave; 30 marzo 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercitazioni (David Benedetti): [[%ATTACHURL%/AssemblerEsercizi30_03_2012.zip][Esercizi di assembly svolti]].
</div>
<br>
<DIV ALIGN="justify">
<B>Luned&igrave; 2 aprile 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Implementazione ad un ciclo di clock dell'ISA di MIPS:
le istruzioni di branch e jump, porzione dell'implementazione per l'esecuzione 
delle istruzioni <code>beq</code> e <code>j</code>; l'unit&agrave; di controllo e lo
schema generale dell'implementazione per l'esecuzione di tutte le istruzioni 
viste (tipo R, <code>add</code>, <code>sub</code>,..., 
accesso alla memoria, <code>lw</code> e <code>sw</code>, branch e jump 
<code>beq</code> e <code>j</code>).
<BR>
<B>Esercizi</B> &nbsp;&nbsp; 
Modificare lo schema generale dell'implementazione (eventualmente aggiungendo linee di controllo,
addizionatori, multiplexer, ecc.) per eseguire le ulteriori istruzioni MIPS (separatamente e poi 
tutte insieme): 
<ol>
<li><code>bgtz</code></li>
<li><code>addi</code></li>
<li><code>ori</code>, <code>andi</code>, <code>xori</code></li>
</ol>
</div>
<br>
<DIV ALIGN="justify">
<B>Venerd&igrave; 13 aprile 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercitazioni (David Benedetti): [[%ATTACHURL%/AssemblerEsercizi16_04_2012.zip][Esercizi di assembly svolti]].
</div>
<br>
<DIV ALIGN="justify">
<B>Luned&igrave; 16 aprile 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Le cinque fasi dell'implementazione ad un ciclo di MIPS. La determinazione della 
lunghezza del ciclo di clock. Svantaggi dell'implementazione ad un ciclo.
<br>
Dal sorgente C all'eseguibile: compilatore, assembler, linker e loader.
Struttura di un <em>object file</em>. Compiti del linker: linking statico
e linking dinamico (cenni).
<br>
Soluzione dell'esercizio <code>bgtz</code> e cenni sulle soluzioni 
degli altri esercizi del 2/4/2012.
<BR>
<B>Esercizio</B> &nbsp;&nbsp; 
Si consideri una nuova istruzione <code>addm d, off(s)</code> che ha l'effetto 
<code>d = d + Mem[s + off]</code>, 
cio&egrave; addiziona al valore del registro <code>d</code> il valore della word
in memoria all'indirizzo dato dalla somma di <code>off</code> e del valore del 
registro <code>s</code>. Implementare <code>addm</code>, 
eventualmente aggiungendo allo schema generale linee di
controllo, addizionatori, multiplexer, ecc. tenendo presente che &egrave; 
rappresentata nel formato I con <code>opcode =
100111</code> (cio&egrave;, un opcode differente da quello di tutte 
le altre istruzioni).
</div>
<br>
<DIV ALIGN="justify">
<B>Venerd&igrave; 20 aprile 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercizi di preparazione alla prova intermedia: [[%ATTACHURL%/ex20_04_2012.pdf][esercizi]] e
[[%ATTACHURL%/ex20_04_2012sol.pdf][soluzioni]].
<BR>
<B>Esercizi</B> &nbsp;&nbsp; 
[[%ATTACHURL%/ex21_04_2012.pdf][Altri esercizi]]
</div>
<br>
<DIV ALIGN="justify">
<B>Venerd&igrave; 4 maggio 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Discussione della soluzione di alcuni esercizi della prova intermedia.
Introduzione al <em>pipelining</em>: stadi dell'esecuzione, miglioramento delle prestazioni
(throughput e latenza), caratteristiche della ISA di MIPS che aiutano il pipeline. 
<em>Pipeline hazards</em>: strutturali, relativi ai dati (cenni sulla tecnica del forwarding) 
e relativi al controllo (possibili approcci: attendere la decisione, 
branch prediction e delayed branch).
</div>
<BR>
<DIV ALIGN="justify">
<B>Luned&igrave; 7 maggio 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Pipelining: introduzione dei registri di pipeline e 
<a href="http://twiki.di.uniroma1.it/pub/Architetture2/MZ/AA11_12_RISORSE/mips_pipe.pdf">schema preliminare</a> 
di implementazione del pipeline senza risoluzione degli hazards.
<BR>
<B>Esercizio</B> &nbsp;&nbsp; 
Determinare gli hazards di ognuno dei seguenti due frammenti di codice e il numero richiesto
di cicli di clock per la loro esecuzione in pipeline secondo lo schema preliminare (considerando gli eventuali
cicli di stallo). 
<table border="1" cellpadding="10">
<tr>
<td>
<pre>
<b>add</b> $s0, $zero, $zero
<b>sub</b> $t1, $t1, $t0
<b>add</b> $t0, $s0, $s0
<b>lw</b> $s2, 40($t1)
<b>add</b> $t1, $t1, $t1
<b>sub</b> $t0, $t0, $t3
<b>sw</b> $s2, 80($t1)
</pre>
</td>
<td>
<pre>
      <b>add</b> $s0, $zero, $zero
      <b>addi</b> $s1, $s0, 100
<i>loop</i>: <b>addi</b> $s0, $s0, 4
      <b>lw</b> $t0, 1024($s0)
      <b>sw</b> $t0, 2048($s0)
      <b>bne</b> $s0, $s1, loop
      <b>sub</b> $s0, $t0, $t2
</pre>
</td>
</tr>
</table>
</div>
<BR>
<DIV ALIGN="justify">
<B>Venerd&igrave; 11 maggio 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzione esercizio. Risoluzione degli hazards sui dati: implementazione del <em>forwarding</em> e 
dell'<em>hazard detection</em>. Hazard sui branch: semplice risoluzione. 
<a href="http://twiki.di.uniroma1.it/pub/Architetture2/MZ/AA11_12_RISORSE/mips_pipe3.pdf">Schema pipeline</a>
cos&igrave; ottenuto. Esempi. Anticipazione della decisione del branch dallo stadio MEM allo stadio EX.
<BR>
<B>Esercizio</B> &nbsp;&nbsp; 
Anticipare la decisione del branch allo stadio ID introducendo un elemento per il test di uguaglianza,
una unit&agrave; di forwarding e modificando l'unit&agrave; di hazard detection. Definire con precisione tutti gli input e output
dei vari elementi introdotti o modificati e la loro logica.
</div>
<BR>
<DIV ALIGN="justify">
<B>Luned&igrave; 14 maggio 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzione esercizio: anticipazione della decisione del branch allo stadio ID.
Esempi. <em>Delayed branch</em> e <em>branch delay slot</em>: discussione dei vantaggi ed esempi.
<a href="http://www.twiki.di.uniroma1.it/pub/Architetture2/MZ/AA11_12_RISORSE/mips_pipe4.pdf">Schema finale</a> 
implementazione in pipeline.
<BR>
<B>Esercizio 1</B> &nbsp;&nbsp; 
Esistono situazioni (cio&egrave;, sequenze di istruzioni) in cui l'unit&agrave; di hazard detection
produce uno stallo quando invece non ce ne sarebbe bisogno?
<br>
<B>Esercizio 2</B> &nbsp;&nbsp; 
Consideriamo il seguente frammento di programma: 
<pre>
      <b>lw</b> $s0, 40($t0)
      <b>sw</b> $s0, 100($t0)
</pre>
Si pu&ograve; eliminare il ciclo di stallo?
<BR>
<B>Esercizio 3</B> &nbsp;&nbsp; 
Determinare il numero di cicli di clock del seguente programma secondo l'ultimo 
schema di implementazione in pipeline:
<pre>
        <b>addi</b> $s0, $zero, 104
        <b>addi</b> $t1, $zero, 4
<i>loop:</i>   <b>addi</b> $s0, $s0, -4
        <b>and</b> $t2, $s0, $t1
        <b>bne</b> $t2, $zero, loop
        <b>lw</b> $t0, 1024($s0)
        <b>add</b> $t3, $t3, $t0
        <b>sw</b> $t0, 2048($s0)
        <b>bne</b> $s0, $zero, loop
        <b>sub</b> $t3, $t3, $t0
</pre>
Se i branch sono delayed, come pu&ograve; l'assembler riordinare le istruzioni e/o aggiungere
<code>nop</code> (mantenendo l'equivalenza con il programma originale) per ottenere le migliori
prestazioni. Determinare il numero di cicli di clock richiesti.
</div>
<BR>
<DIV ALIGN="justify">
<B>Venerd&igrave; 18 maggio 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzione esercizi. <em>Eccezioni</em>: esempi, classificazione. Modalit&agrave; operative: <em>User Mode</em>
e <em>Kernel Mode</em>. I registri <em><code>EPC</code></em> e <em><code>Status</code></em> del Coprocessore 0 di MIPS.
</div>
<BR>
<DIV ALIGN="justify">
<B>Luned&igrave; 21 maggio 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Ordinamento della gestione delle eccezioni. Implementazione nella pipeline delle eccezioni:
il registro <em><code>Cause</code></em>, modifica del controllo.
<br>
Introduzione alla gerarchia delle memorie e alla memoria <em>cache</em>.
<BR>
<B>Esercizio</B> &nbsp;&nbsp; 
Si consideri il seguente programma in cui l'esecuzione delle istruzioni provoca le eccezioni 
indicate:
<pre>
    <b>lw</b> $s0, 40($t0)         <span style="color:ff0000">#Page Fault nell'accesso alla memoria dati</span>
    <b>add</b> $s1, $s0, $s0       <span style="color:ff0000">#Overflow</span>
    <b>sub</b> $s1, $s1, $t1       <span style="color:ff0000">#Page Fault in lettura dell'istruzione</span>
</pre>
Determinare il numero totale di cicli richiesto per l'esecuzione sapendo che 
gli exception handler per la gestione dei Page Fault richiedono ciascuno 100 cicli
e quello per l'Overflow richiede 50 cicli di clock.
</div>
<BR>
<DIV ALIGN="justify">
<B>Venerd&igrave; 25 maggio 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzione esercizio. Memoria cache: <em>blocchi</em> (o <em>linee</em>) 
<em>hit</em>, <em>miss</em>, <em>hit rate</em>, 
<em>miss rate</em>, <em>hit time</em>, <em>miss penalty</em>. 
Organizzazione di una cache: a <em>mappatura diretta</em> (direct mapped cache),
indice, <em>tag</em>, byte offset e bit di validit&agrave;. Gestione dei miss.
Gestione delle scritture: <em>write-through</em> con <em>write buffer</em>, 
<em>write-back</em>. Stima delle prestazioni.
<BR>
<B>Esercizio 1</B> &nbsp;&nbsp; 
Per una cache a mappatura diretta con 4 blocchi di 8 word, inizialmente vuota,
si consideri la seguente serie di accessi a word di 32 bit in memoria: 
8, 12, 44, 64, 84, 52, 256, 192, 76, 44, 12, 88, 16, 300, 44 (gli indirizzi sono a 
byte). Quali accessi sono miss e quali hit.
<br>
Sapendo che gli indirizzi sono di 32 bit, da quanti bit e formata la cache?
<BR>
<B>Esercizio 2</B> &nbsp;&nbsp; 
Un computer pu&ograve; essere dotato con uno dei due seguenti sistemi di memoria. 
<ol>
<li>Memorie cache (istruzioni e dati) con blocchi da 16 words con le seguenti prestazioni: 
<ul>
<li>miss rate per le istruzioni 4%</li>
<li>miss rate per i dati 8%</li>
<li>miss penalty 100 cicli di clock</li>
</ul>
</li>
<li>
Memorie cache (istruzioni e dati) con blocchi da 64 words con le seguenti prestazioni: 
<ul>
<li>miss rate per le istruzioni 2%</li>
<li>miss rate per i dati 6%</li>
<li>miss penalty 200 cicli di clock</li>
</ul>
</li>
</ol>
Sapendo che la frequenza delle istruzioni che accedono alla memoria (lettura/scrittura
dati) &egrave; del 20%, quale dei due sistemi garantisce le migliori prestazioni?
</div>
<BR>
<DIV ALIGN="justify">
<B>Luned&igrave; 28 maggio 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzione esercizi. Cache associative: <em>fully associative</em>, <em>n-way set associative</em>.
Esempi. Cenni su cache multilivello.
<BR>
<B>Esercizio</B> &nbsp;&nbsp; 
Si consideri una cache 2-way set associative con 4 insiemi, blocchi da 4 words e con
strategia di sostituzione LRU. Quali accessi sono miss e quali hit nella seguente
serie di accessi a word in memoria: 52, 12, 24, 112, 16, 180, 116, 52, 80, 84, 60 
(gli indirizzi sono a byte). La cache &egrave; inizialmente vuota.
<br>
Sapendo che gli indirizzi sono di 32 bit e che un bit per insieme &egrave; sufficiente per
implementare l'LRU, da quanti bit e formata la cache?
</div>
<BR>
<DIV ALIGN="justify">
<B>Venerd&igrave; 1 giugno 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Soluzione esercizio. Memorie cache multilivello: prestazioni ed esempio.
Memoria virtuale: cenni storici e motivazioni. Spazio di indirizzi virtuale,
pagine virtuali, Page Table, traduzione, Page Faults. Supporto hardware: TLB (Translation Lookaside Buffer).
<BR>
<B>Esercizio</B> &nbsp;&nbsp; 
Si consideri il seguente programma:
<pre>
    long i, s = 0;
    for (i = 0 ; i < 2048 ; i++)
        s += A[i];
</pre>
Sapendo che <code>A</code> &egrave; un array di 2048 interi, 
sapendo che la cache &egrave; 4-way set associative con 1024 insiemi
e blocchi da 128 words, che la memoria virtuale ha pagine da 4KB, che il programma e l'array 
sono allineati a un multiplo di 4K e che sono su pagine di memoria virtuale diverse, 
e assumendo che <code>i</code> e <code>s</code> sono mappati
su registri:
<ol>
<li>Quanti sono i miss sulla cache per l'accesso all'array?</li>
<li>Quanti sono i miss sulla TLB in totale?</li>
<li>Che succederebbe alle prestazioni di questo programma se non ci fosse 
una TLB?</li>
</ol>
Si assume che la cache e la TLB siano inizialmente vuoti e che la TLB 
abbia una capacit&agrave; di almeno 16.
</div>
<BR>
<DIV ALIGN="justify">
<B>Luned&igrave; 4 giugno 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Gestione page fault. Funzione di protezione della memoria virtuale. Soluzione esercizio. 
Esercizio 1 in  [[%ATTACHURL%/ex04_06_2012.pdf][Esercizi_04_giugno_2012]].
<BR>
<B>Esercizio</B> &nbsp;&nbsp; 
Esercizio 2 in [[%ATTACHURL%/ex04_06_2012.pdf][Esercizi_04_giugno_2012]].
</div>
<BR>
<DIV ALIGN="justify">
<B>Venerd&igrave; 8 giugno 2012</B>&nbsp;&nbsp;&nbsp;&nbsp;
Esercizi di preparazione alla prova finale: [[%ATTACHURL%/ex08_06_2012.pdf][Esercizi]].
Soluzioni dei primi due esercizi: [[%ATTACHURL%/ex08_06_2012sol.pdf][Soluzioni]].
</div>
</div>
This topic: Architetture2/MZ > Architetture2 > AA11_12 > AA11_12_DIARIO
Topic revision: r28 - 2012-06-08 - RiccardoSilvestri