Architettura degli Elaboratori a.a. 2011-2012 (canale M-Z)

Lunedì 5 marzo 2012     Informazioni sul corso e brevissima panoramica dei contenuti del corso. Cenni sulla storia dei computer: dall'ENIAC al Pentium, passando per il MIPS. Il concetto di stored program. L'architettura di un computer e i suoi aspetti: ISA (Instruction Set Architecture), organizzazione e hardware. Caratteristiche che distinguono le architetture.

• Tipo della memoria interna: accumulator, stack, extended accumulator (o special-purpose registers), general-purpose registers (GPR).
• Tipo di accesso alla memoria: register-memory e load-store.
• Complessità dell'insieme delle istruzioni: CISC (Complex Instruction Set Computer) e RISC (Reduced Instruction Set Computer).

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.

Venerdì 9 marzo 2012     Vista dall'alto di un computer (architettura di von Neumann). Le proprietà che caratterizzano una architettura RISC e le tipologie delle istruzioni: istruzioni ALU, trasferimento dati e salti condizionati (branches) e non (jumps). I registri e le prime istruzioni MIPS: add, addi, sub. Rappresentazione in memoria delle istruzioni. Formati R, I e J. Istruzioni di branch e jump: beq, bne, bgez, bgtz, blez, bltz, j. Alcune pseudo-istruzioni del linguaggio assembly del MIPS: li, move, bge, bgt, ble, blt. Esempi: programma che calcola il massimo di tre numeri e programma che calcola il k-esimo numero di Fibonacci (algoritmo iterativo).
Esercizio    Scrivere un programma che ordina, in senso cresente, i numeri in $s0, $s1, $s2. Al termine dell'esecuzione in $s0, $s1, $s2 ci devono essere i tre numeri ordinati.

Lunedì 12 marzo 2012     Soluzione dell'esercizio. Le istruzioni slt, slti e cenni sull'implementazione delle pseudo-istruzioni di branch. Le istruzioni logiche: and, andi, or, ori, xor, xori, nor (la pseudo-istruzione not). Le istruzioni di shift: sll, srl, sllv, srlv. Esempio: conteggio dei bit 1 in una word (registro). Istruzioni per il trasferimento dei dati: lw, sw. Convenzioni MIPS per l'uso della memoria: Segmento Testo, Segmento Dati, Heap e Stack. Alcune direttive dell'assembler: .data, .word, .text. Esempio: somma dei valori di un array nel Segmento Dati.
Esercizio    Scrivere un programma che, dato un array nel Segmento Dati, incrementa di 1 tutti gli elementi dell'array.

Venerdì 16 marzo 2012     Esercitazioni (David Benedetti): Esercizi di assembly svolti.

Lunedì 19 marzo 2012     Soluzioni esercizio (12/3/2012): tramite indici e tramite puntatori. Procedure e il supporto per la loro chiamata: istruzioni jal, jr e il registro $ra. Registri per i parametri $a0-$a3 e per i valori ritornati $v0,$v1. 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 Stack e il registro $sp. Esempio di procedura che chiama un'altra procedura: procedura che ordina un array tramite selection-sort. Cenni sulla implementazione di procedure ricorsive.
Esercizio    Scrivere una procedura che calcola il fattoriale in modo ricorsivo.

Venerdì 23 marzo 2012     Soluzione esercizio: istruzione mul. 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 (Clock cycles Per Instruction). 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 (add, sub, ecc.); implementazione del blocco dei registri.
Esercizio    Implementare una procedura per la ricerca binaria ricorsiva: a0: puntatore al primo elemento; a1: puntatore all'ultimo elemento; a2: valore cercato; v0: ritorna il puntatore all'elemento con il valore cercato o 0 se non esiste.

Lunedì 26 marzo 2012     Soluzione esercizio. Implementazione ad un ciclo di clock dell'ISA di MIPS: le istruzioni di accesso alla memoria (lw, sw), porzione dell'implementazione per l'esecuzione sia delle istruzioni di tipo R che di quelle che accedono alla memoria.

Venerdì 30 marzo 2012     Esercitazioni (David Benedetti): Esercizi di assembly svolti.

Lunedì 2 aprile 2012     Implementazione ad un ciclo di clock dell'ISA di MIPS: le istruzioni di branch e jump, porzione dell'implementazione per l'esecuzione delle istruzioni beq e j; l'unità di controllo e lo schema generale dell'implementazione per l'esecuzione di tutte le istruzioni viste (tipo R, add, sub,..., accesso alla memoria, lw e sw, branch e jump beq e j).
Esercizi    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):

1. bgtz
2. addi
3. ori, andi, xori

Venerdì 13 aprile 2012     Esercitazioni (David Benedetti): Esercizi di assembly svolti.

Lunedì 16 aprile 2012     Le cinque fasi dell'implementazione ad un ciclo di MIPS. La determinazione della lunghezza del ciclo di clock. Svantaggi dell'implementazione ad un ciclo.
Dal sorgente C all'eseguibile: compilatore, assembler, linker e loader. Struttura di un object file. Compiti del linker: linking statico e linking dinamico (cenni).
Soluzione dell'esercizio bgtz e cenni sulle soluzioni degli altri esercizi del 2/4/2012.
Esercizio    Si consideri una nuova istruzione addm d, off(s) che ha l'effetto d = d + Mem[s + off], cioè addiziona al valore del registro d il valore della word in memoria all'indirizzo dato dalla somma di off e del valore del registro s. Implementare addm, eventualmente aggiungendo allo schema generale linee di controllo, addizionatori, multiplexer, ecc. tenendo presente che è rappresentata nel formato I con opcode = 100111 (cioè, un opcode differente da quello di tutte le altre istruzioni).

Venerdì 20 aprile 2012     Esercizi di preparazione alla prova intermedia: esercizi e soluzioni.
Esercizi    Altri esercizi

Venerdì 4 maggio 2012     Discussione della soluzione di alcuni esercizi della prova intermedia. Introduzione al pipelining: stadi dell'esecuzione, miglioramento delle prestazioni (throughput e latenza), caratteristiche della ISA di MIPS che aiutano il pipeline. Pipeline hazards: strutturali, relativi ai dati (cenni sulla tecnica del forwarding) e relativi al controllo (possibili approcci: attendere la decisione, branch prediction e delayed branch).

Lunedì 7 maggio 2012     Pipelining: introduzione dei registri di pipeline e schema preliminare di implementazione del pipeline senza risoluzione degli hazards.
Esercizio    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).

add $s0, $zero, $zero sub $t1, $t1, $t0 add $t0, $s0, $s0 lw $s2, 40($t1) add $t1, $t1, $t1 sub $t0, $t0, $t3 sw $s2, 80($t1)

add $s0, $zero, $zero addi $s1, $s0, 100 loop: addi $s0, $s0, 4 lw $t0, 1024($s0) sw $t0, 2048($s0) bne $s0, $s1, loop sub $s0, $t0, $t2

Venerdì 11 maggio 2012     Soluzione esercizio. Risoluzione degli hazards sui dati: implementazione del forwarding e dell'hazard detection. Hazard sui branch: semplice risoluzione. Schema pipeline così ottenuto. Esempi. Anticipazione della decisione del branch dallo stadio MEM allo stadio EX.
Esercizio    Anticipare la decisione del branch allo stadio ID introducendo un elemento per il test di uguaglianza, una unità di forwarding e modificando l'unità di hazard detection. Definire con precisione tutti gli input e output dei vari elementi introdotti o modificati e la loro logica.

Lunedì 14 maggio 2012     Soluzione esercizio: anticipazione della decisione del branch allo stadio ID. Esempi. Delayed branch e branch delay slot: discussione dei vantaggi ed esempi. Schema finale implementazione in pipeline.
Esercizio 1    Esistono situazioni (cioè, sequenze di istruzioni) in cui l'unità di hazard detection produce uno stallo quando invece non ce ne sarebbe bisogno?
Esercizio 2    Consideriamo il seguente frammento di programma:

      lw $s0, 40($t0)
      sw $s0, 100($t0)

Si può eliminare il ciclo di stallo?
Esercizio 3    Determinare il numero di cicli di clock del seguente programma secondo l'ultimo schema di implementazione in pipeline:

        addi $s0, $zero, 104
        addi $t1, $zero, 4
loop:   addi $s0, $s0, -4
        and $t2, $s0, $t1
        bne $t2, $zero, loop
        lw $t0, 1024($s0)
        add $t3, $t3, $t0
        sw $t0, 2048($s0)
        bne $s0, $zero, loop
        sub $t3, $t3, $t0

Se i branch sono delayed, come può l'assembler riordinare le istruzioni e/o aggiungere nop (mantenendo l'equivalenza con il programma originale) per ottenere le migliori prestazioni. Determinare il numero di cicli di clock richiesti.

Venerdì 18 maggio 2012     Soluzione esercizi. Eccezioni: esempi, classificazione. Modalità operative: User Mode e Kernel Mode. I registri EPC e Status del Coprocessore 0 di MIPS.

Lunedì 21 maggio 2012     Ordinamento della gestione delle eccezioni. Implementazione nella pipeline delle eccezioni: il registro Cause, modifica del controllo.
Introduzione alla gerarchia delle memorie e alla memoria cache.
Esercizio    Si consideri il seguente programma in cui l'esecuzione delle istruzioni provoca le eccezioni indicate:

    lw $s0, 40($t0)         #Page Fault nell'accesso alla memoria dati
    add $s1, $s0, $s0       #Overflow
    sub $s1, $s1, $t1       #Page Fault in lettura dell'istruzione

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.

Venerdì 25 maggio 2012     Soluzione esercizio. Memoria cache: blocchi (o linee) hit, miss, hit rate, miss rate, hit time, miss penalty. Organizzazione di una cache: a mappatura diretta (direct mapped cache), indice, tag, byte offset e bit di validità. Gestione dei miss. Gestione delle scritture: write-through con write buffer, write-back. Stima delle prestazioni.
Esercizio 1    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.
Sapendo che gli indirizzi sono di 32 bit, da quanti bit e formata la cache?
Esercizio 2    Un computer può essere dotato con uno dei due seguenti sistemi di memoria.

1. Memorie cache (istruzioni e dati) con blocchi da 16 words con le seguenti prestazioni:
   • miss rate per le istruzioni 4%
   • miss rate per i dati 8%
   • miss penalty 100 cicli di clock
2. Memorie cache (istruzioni e dati) con blocchi da 64 words con le seguenti prestazioni:
   • miss rate per le istruzioni 2%
   • miss rate per i dati 6%
   • miss penalty 200 cicli di clock

Sapendo che la frequenza delle istruzioni che accedono alla memoria (lettura/scrittura dati) è del 20%, quale dei due sistemi garantisce le migliori prestazioni?

Lunedì 28 maggio 2012     Soluzione esercizi. Cache associative: fully associative, n-way set associative. Esempi. Cenni su cache multilivello.
Esercizio    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 è inizialmente vuota.
Sapendo che gli indirizzi sono di 32 bit e che un bit per insieme è sufficiente per implementare l'LRU, da quanti bit e formata la cache?

Venerdì 1 giugno 2012     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).
Esercizio    Si consideri il seguente programma:

    long i, s = 0;
    for (i = 0 ; i < 2048 ; i++)
        s += A[i];

Sapendo che A è un array di 2048 interi, sapendo che la cache è 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 i e s sono mappati su registri:

1. Quanti sono i miss sulla cache per l'accesso all'array?
2. Quanti sono i miss sulla TLB in totale?
3. Che succederebbe alle prestazioni di questo programma se non ci fosse una TLB?

Si assume che la cache e la TLB siano inizialmente vuoti e che la TLB abbia una capacità di almeno 16.

Lunedì 4 giugno 2012     Gestione page fault. Funzione di protezione della memoria virtuale. Soluzione esercizio. Esercizio 1 in Esercizi_04_giugno_2012.
Esercizio    Esercizio 2 in Esercizi_04_giugno_2012.

Venerdì 8 giugno 2012     Esercizi di preparazione alla prova finale: Esercizi. Soluzioni dei primi due esercizi: Soluzioni.