Architettura degli elaboratori Turno 3/2005-2006

News

• FISSATO L'APPELLO Di GIUGNO PER IL GIORNO 19 (è già possibile iscriversi sul SIFA)

Anni precedenti

• Diario del corso 2003/2004
• Filez anni precedenti

Informazioni generali

Docenti

---

Prof. D'Antona / Prof. Marra per il laboratorio.

Corsi di laurea

---

• Informatica

Modalità d'esame

---

Orale + Progetto

dal sito ufficiale: L'esame ha cadenza mensile, tendenzialmente di lunedì. Le date degli appelli sono pubblicate sul sito del D.I.Co. Il voto è determinato da due prove. Una è un'interrogazione tradizionale sugli argomenti trattati a lezione. La seconda consiste nella stesura di una porzione di programma in linguaggio Assembly MIPS . Le due prove possono essere sostenute indipendentemente, purché a non più di 12 mesi l’una dall’altra, pena la necessità di ripetere la prova già sostenuta. Il voto per entrambe le prove è in trentesimi. Il voto finale, che potrà essere registrato solo dopo aver sostenuto con successo entrambe le prove, è ottenuto per media pesata dai due voti parziali. Il peso del progetto in Assembly è di un terzo del totale. Il tema del progetto è pubblicato su la pagina ufficiale del corso tre volte l’anno, all’inizio dei quadrimestri gennaio-aprile, maggio-luglio, settembre-dicembre. Il candidato può consegnare in qualunque momento per posta elettronica all’indirizzo marra@dico.unimi.it l’elaborato relativo al tema d’esame corrente. Per poter registrare il voto finale in un dato appello, tuttavia, occorre consegnare il progetto una settimana prima dell’appello in questione, per dare il tempo ai docenti di valutare l’elaborato; le scadenze precise relative agli appelli correnti sono riportate nel tema d’esame. L’elaborato deve consistere di un solo file di testo contenente il sorgente Assembly, eventualmente corredato da un secondo file contenente la documentazione, in formato testo, Adobe PDF, o Rich Text Format.

---

Orari e luogo delle lezioni

Martedì	Giovedì
18:30-21:30 Aula 200 (via Golgi)	18:30-21:30 Aula 200 (via Golgi)

Orario di ricevimento studenti

Lunedì 12.00 - 14.00

Informazioni specifiche

Sito del corso

SITO UFFICIALE DEL CORSO

Forum del corso, e affini

Forum su DSY.IT

Materiale Didattico

Programma del corso

Non ancora disponibile

TESTI

---

Testo di riferimento

• STRUCTURED COMPUTER ORGANIZATION 5 edizione autore Tanenbaum

la versione italiana del libro è in stampa in questi giorni

---

Altri testi Consigliati

• • D.A. Patterson, J.L. Hennessy, Struttura, organizzazione e progetto dei calcolatori: interdipendenza tra hardware e software, Jackson libri, Milano, 1999 (seconda edizione).
  • Per le reti di calcolatori: D. Comer, Internet e reti di calcolatori, Addison Wesley-Pearson Italia, Milano, 2003 (terza edizione).
  • Il testo: O. D'Antona, E. Damiani, Ambienti esecutivi e di sviluppo dei linguaggi di programmazione, Addison Wesley-Masson, Milano, 1992, è una semplice introduzione preliminare agli argomenti del corso.

---

Video delle lezioni

Le Lezioni saranno registrate durante il semestre e rese fruibili sul sito Virtual Classroom

NB. è necessario un account SILAB per accedere al sito

NB2 le lezioni dovrebbero essere online 7/10 giorni dopo la loro registrazione

Appunti

Appunti del corso a cura di Paolo Pavan:

Parte 1

Parte 2

Completi

Appunti del corso a cura di Fabio:

appunti di Fabio

MIPS

Convenzioni MIPS per il passaggio dei parametri discusse a lezione

Altro materiale in Internet

• Il Simulatore SPIM e relativa documentazione

• Un utile ambiente di sviluppo gratuito (SO Windows), detto MIPSter, espressamente pensato per il simulatore SPIM (e l’assembly MIPS) è scaricabile da qui

• A questo indirizzo si trovano le pagine ufficiali su MIPSter

• Un versione dello SPIM per MacOS si trova a questoindirizzo, a cura di Daniel Franke

• Un buon editor gratuito è ConTEXT, reperibile a questo indirizzo. È prevista una modalità di evidenziazione della sintassi orientata all’assembly MIPS.

• Multipiattaforma trovate jEdit (in java), con parziale supporto alla sintassi MIPS

Esami passati, tesine, compiti ..

Progetti anni passati

Diario del corso

Lezione Giovedì 9 Marzo 2006

---

• Introduzione al corso

• Algebra di Boole

• • Le funzioni Booleane

• • tabelle di verità

• • i mintermini

si consigliano gli appunti reperibili dal sito ufficiale del corso a questo link

Lezione Martedì 14 Marzo 2006

---

• Ripasso lezione precedente
  • Funzioni booleane (le funzioni booleane sono funzioni che ricevono in ingresso una nupla di 0,1 e restituiscono un BIT 0,1)
  • I Mintermini(il mintermine è una funzione booleane che assume il valore 1 in corrispondenza di un unica configurazione di ingressi)

• Rapresentazione tramite diagramma di Venn di funzioni booleane

• Analogie fra funzioni Booleane e calcolo proposizionale (Una proposizione cioè una 'frase' da cui analogamente alle funzioni booleane ci si può aspettare 2 soli risultati Vero o Falso)

• • la congiunzione logica
  • la disgiunzione logica
  • la negazione logica

• Accenni storici a Kurt Goedel e la Logica Polivalente

• Le Analogie con i circuiti

• Le porte Logiche ( logical Gate)

• cenni storici su Vanner Bush (padre dei calcolatori anologici), e su Claude Shannon (suo alievo che formalizzò la corrispondenza fra calcolo proposizionale e Circuiti)

• le leggi di De Moorgan

• Riassunto Altre prinicpali propietà Algebra Booleana(elemento neutro delle operazioni , distributiva , assorbimento ....)

• AND

$A$	$B$	$A$ ∧ $B$
F	F	F
F	T	F
T	F	F
T	T	T

OR

$A$	$B$	$A$ ∨ $B$
F	F	F
F	T	T
T	F	T
T	T	T

NOT

$A$	¬ $A$
F	T
T	F

funzionalmente completi (sono cioè sufficenti ad esprimere una qualsiasi funzioni booleana

• NOT e AND/ NOT e OR sarebbero già sufficenti a esprimere qualsiasi espressione booleana (Dimostrazione usando De Morgan)

• La porta NAND da sola è sufficente ad esprimere qualsiasi funzione booleana

Sapendo che a NAND b = NOT( a AND b ) possiamo dimostrare che:

La funzione NOT a è esprimibile come a NAND a

NOT a = NOT( a AND a ) [ per idempotenza a AND a = a ]

NOT( a AND a ) = a NAND a [ per la definizione sopra ]

La funzione a AND b è esprimibile come ( a NAND b ) NAND ( a NAND b )

a AND b = NOT( NOT( a AND b ) ) [ per idempotenza NOT( NOT a ) = a ]

NOT( NOT( a AND b ) ) = NOT( a NAND b ) [ per la definizione sopra ]

NOT( a NAND b ) = ( a NAND b ) NAND ( a NAND b ) [ per la definizione di NOT utilizzando un NAND ]

La funzione a OR b è esprimibile come ( a NAND a ) NAND ( b NAND b )

a OR b = NOT( NOT( a ) ) OR NOT( NOT( b ) ) [ per idempotenza NOT( NOT a ) = a ]

NOT( NOT( a ) ) OR NOT( NOT( b ) ) = NOT( NOT( a ) AND NOT( b ) ) [ legge di De Morgan ]

NOT( NOT( a ) AND NOT( b ) ) = NOT( a ) NAND NOT( b ) [ per la definizione sopra ]

NOT( a ) NAND NOT( b ) = ( a NAND a ) NAND ( b NAND b ) [ per la definizione di NOT utilizzando un NAND ]

• Rappresentazione grafica dei circuiti

• Il Multiplexer e la sua rappresentazione

• il DeMultiplexer

• esempio del loro uso combinato per la condivisione di una linea telefonica

DA FARE / DA PENSARE:

---

1)abbiamo visto che usando solo AND e OR non riusciamo ad esprimere tutte le possibili funzioni booleane, Quali e Quante funzioni riusciamo ad esprimere?

Lezione Giovedì 16 Marzo 2006

---

• tabella riassuntiva

Insieme Connettori	Funzionalmente completo	Minimale	Minimo
AND,OR,NOT	SI	NO	NO
AND,NOT	SI	SI	NO
OR,NOT	SI	SI	NO
NAND	SI	SI	SI

• ripasso Multiplexer (o selettore)

• Multiplexer con + di 2 ingressi
  • Visto circuito Multiplexer a 3 Ingressi

• La formula per determinare il numero di variabili necessarie in un Multiplexer ad n ingressi (ceiling di Logaritmo in base 2 di n)
  • il ceiling ed il flor di un numero reale

• IL DECODER o decodificatore

• • Tabella di verità di un decoder 2 ingressi 4 uscite

• Usare il decodificatore assieme al multiplexer (altra forma di multiplexer a più ingressi)

• primo Teorema della rappresentazione canonica di funzioni Booleane:

Qualunque funzione di n variabili può essere scritta univocamente come somma di j (j numero intero) prodotti di n variabili asserite o negate

o in altra forma:

Qualsiasi funzione booleana può essere espressa univocamente come somma di mintermini)

• Esempio con grafico di Venn

• Metodo per ottenere in forma canonica una funzione Booleana a partire dalla tabella di verità
  • Esembio con tabella Multiplexer

• Applicazioni pratiche del teorema della forma canonica:
  • PLA(Programmable Logic Array)

• il FULL ADDER (sommatore di BIT)

• Accenni alle funzioni booleane monotome

Lezione Martedì 21 Marzo 2006

---

• Esercizio di ripasso : caratterizazione del mintermine $P2^{n}-1$

• Casi particolari Multiplexer (2 ingressi a,b e "selettore" S):
  • 2 ingressi uguali
  • b = S
  • a = s
  • a = 0 , b = 1

• Diagramma su le possibili uscite da un multiplexer (2 ingressi a,b e "selettore" S)

• Esercizio svolto in classe: Costruire la tabella di verità di un circuito proposto e usando la tabella scrivere la funzione booleana rapresentata dal circuito

• I Maxtermini
• Forma canonica duale (POS Product Of (Complete) Sums)
  • SOP (Sum Of (Complete) products) è basata su mintermine
  • POS (POS Product Of (Complete) Sums) è basata sui maxtermini
• XOR(eXclusive OR)
• il circuito COMPARATORE
  • Esempio compara 1 singolo bit
  • Esempio Comparatore n-uple di 3 bit
• il circuito SHIFTER (traslatore)
• Differenza Logica fra Data-Path e Control-Path
• Un sommatore completo/FULL ADDER (con carry-in e carry-out) realizzato con 2 XOR
• Esempio sommatore a 16 BIT con ottimizzazione (esecuzione in parallelo di una parte del calcolo - il secondo "ottetto" esegue contemporaneamente al primo ottetto il calcolo con carry-in 1 - il terzo otteto esegue il calcolo con carry-in 0 (tengo solo la soluzione che mi interessa senza aspettare riporto in uscita )
• Cenni su l'esecuzione speculativa
• Esempio di circuito Moltiplicatore con registry a 64bit
• Esempio ottimizzazione con registry a 32bit

Lezione Giovedì 23 Marzo 2006

---

Lezione rinviata come da preavviso

Lezione Martedì 28 Marzo 2006

---

• Esempio Moltiplicatore

• Aritmetica Binaria
  • Gli interi rapresentati in base 2
  • Gli interi in genere in base n
  • Conversioni da decimale a base n e viceversa

• La Notazione Complemento a 2
  • L'opposto in complemento a 2
  • Sottrazione in Complemento a 2

• L'Overflow nell'aritmetica complemento a 2 ed il relativo controllo

Lezione Giovedì 30 Marzo 2006

---

• Ripasso Aritmetica Binaria/Complemento a 2

• Un Importante Propietà dei numeri complemento a 2 L' ESTENSIONE DEL SEGNO(Es. 1010 = 11010 = 111010....)

• Esercizio Un Calendario Digitale (Tabella di Verità)

• dai CIRCUITI COMBINATORI AI CIRCUITI SEQUENZIALI
  • il concetto di stato di un circuito

• Il circuito SR(Set and Reset)
  • il concetto di memoria

• il circuito LATCH D o BAT (Bistabile Asincrono Trasparente)
  • Esempio di funzionamento

• il FLIP FLOP (sincrono!)
  • Esempio di Funzionamanto

---

Lezione Martedì 4 Aprile 2006

• Lo Shifter (ripasso)

• I Registri (ripasso)

• Shift register

• Gli automi a stati finiti

• Esempio : l'automa a stati finiti che rappresenta il latch-d

• Metodi per "passare" dall'automa a stati finiti al circuito
  • Calcolo del numero di Bistabili necessari a rapresentare gli stati dell'automa
  • Progetttazione della rete combinatoria di pilotaggio

• Domanada: Quante sono le stringhe binarie di lunghezza finita?
  • risposta: ALEPH con 0
  • inciso sui diversi tipi di infinito

• Ulteriore Automa d'esempio:
  • Pensiamo di voler costruire un circuito che riceva ogni x millesecondi un dato , questo circuito deve riconoscere quando gli ultimi 3 bit che ha ricevuto sono tutti e tre 1 , nel qual caso deve accendere una lampadina

Lezione Giovedì 6 Aprile 2006

---

• Formalizzazione degli automi a stati finiti

• il Register File - RF
  • Il circuito di scrittura dell' RF
  • Il circuito di lettura dell' RF
• I SISTEMI DI MEMORIA
  • SRAM
  • DRAM
• La macchina di Von Neumann
  • la fase di fetch
  • la fase esecutiva

• La comunicazione tra memoria e processore:IL BUS
• I tre sottoinsiemi logici del BUS:
  • BUS DATI
  • BUS INDIRIZZI
  • BUS DI CONTROLLO
• Altri dispositivi di memorizzazione:

• i dischi magnetici
  • settori, tracce e cilindri
  • i sistemi RAID
• i cd

Lezione Martedì 11 Aprile 2006

---

lezione annullata per concomitanza con esame (come da preavviso)

Lezione Giovedì 13 Aprile 2006

---

Lezione Non svolta come da calendario accademico

Lezione Martedì 18 Aprile 2006

---

Lezione Non svolta come da calendario accademico

Lezione Giovedì 20 Aprile 2006

---

• L'INSTRUCTION REGISTER

• Esempio didattico con istruzioni a lunghezza fissa a 16 BIT

• LA FASE DI FETCH

• IL PROGRAM COUNTER

• la ALU
  • la ALU nel nostro esempio didattico a 16 bit
  • la prima cella della ALU
  • le successive celle della ALU

• Le 2 Funzioni del RF
  • sorgente dei Dati
  • destinazione dei dati

• Accenni all'architettura PIPELINE

• processori con istruzioni a lunghezza fissa(ULTRASPARC 3) / e variabile (pentium 4)
  • i vantaggi di avere istruzioni a lunghezza fissa

• cenni su microprogrammi e firmware

• Acceni storici alla nascita dei processori RISC

• IL MAR (Memory Adress Register)

• MDR (Memory Data Register)

Lezione Martedì 25 Aprile 2006

---

Lezione Non svolta come da calendario accademico

Lezione Giovedì 27 Aprile 2006

---

• esempio di commutazione "level triggered" (innescato usando uno "spike" causato dal ritardo di commutazione di un invertitore)

• Esempio: Automa a stati finiti di una machinetta del caffè

• la catena di compilazione
  • l'Analizzatore lessicale

• Automa a stati finiti di un analizzatore lessicale (di un linguaggio modulo a 2)

• La tabella dei simboli del compilatore
  • I tipi di dato (2 informazioni (a)occupazione memoria, (b)operazioni che posso compiere)
• Esempio: rappresentazione in Pascal di una stringa - utilizzo della memoria

• I Limiti degli Automi a stati finiti
  • Esempio: (non è possibile costruire un automa a stati finiti che riconosca stringe binarie di lungheza arbitraria del tipo 0^n 1^n cioè stringhe con n zeri seguiti da n 1)

Lezione Martedì 02 Maggio 2006

---

• IL LINGUAGGIO MACCHINA

• Un Ipotesi di Linguaggio macchina per una architettura rigorosamente a 32BIT (i fogli che descrivono questo linguaggio macchina didattico sono stati distribuiti dal prof. D'Antona)
  • Il Codice Operativo nel nostro Linguaggio Macchina didattico
    • and , or , add , sub , slt
  • gli altri BIT dell'Instruction Register: rs,rt,rd
  • Branch on equal
  • Bne Branch on not equal
  • l'OFFSET (rappresentato come intero a complemento a 2, usando i 16 bit meno significativi dell'IR)
  • Le istruzioni LOAD e STORE

• Esempio: Scrittura di un semplice programma usando il linguaggio macchina appena definito

• Simulazione "personificata" passo passo del funzionamento del nostro programma di esempio scritto in linguaggio macchina (programma che calcola la somma un array di numeri interi)

• il LOADER

• il loader ed il program counter

• L'assemblatore a due passate
  • La prima passata
    • Gestione delle etichette GOTO
    • la tabella delle etichette
  • La seconda passata
    • gestione dei salti incrementando o decrementando il program counter (OFFSET = ValoreTabella - Valore corrente di Line)

Lezione Giovedì 04 Maggio 2006

---

• Il Compilatore ad una passata

• Il circuito che esegue l'istruzione LOAD

• Il circuito che esegue l'istruzione STORE

• Il circuito che esegue l'estensione del segno

• Il circuito che esegue l'istruzione BRANCH ON EQUALS

  Domanda: Durante l'esecuzione di sub R3 R3 R3 quanto vale OFFSETX4?
  (è chiaro che OFFSETx4 Non viene usato durante sub ma la domanda è che bit si trovano in quel momento in OFFSETX4!! non l'utilizzo o meno di questi       bit)

Lezione Martedì 09 Maggio 2006

---

• Cenni su la storia e l'architettura dei 3 processori trattati nel libro: PENTIUM 4 - ULTRA SPARC III - 8051
  • Intel dal 4004 al Pentium 4 (caratteristiche ed evoluzione dei processori Intel)
  • cenni sull'architettura del Pentium 4
    • l'Out of Order Control (controllo fuori sequenza)
  • SUN e la nascita dell'architettura SPARC (basato su RISC)
  • il processore 8051 usato nei sitemi integrati (cioè telefonini elettrodomestici...)
    • caratteristiche di questo microprocessore
    • l'ambiente di sviluppo per questi processori

• Gestione dell'Input/Output
  • Polling
  • Int. driver IO
  • DMA

• ARCHITETTURA PIPELINE
  • Organizzazione del ciclo esecutivo in 5 fasi( FETCH - Decodifica/Lettura IR - ALU -MEM -Write Back)
  • il parallelismo esecutivo alla base del concetto di PIPELINE
  • le tempistiche : confronto PIPELINE/NON PIPELINE
  • I Registri di interfaccia

 Domanda: da dove arriva Il RegWrite dell'RF in archiettura PIPELINE? Risp. anche questo è salvato   
 nel registro di input del WriteBacK

Lezione Giovedì 11 Maggio 2006

---

Prima Lezione di Assembly tenuta dal dot. V.Marra

• Introduzione al ciclo di lezione su la programmazione in assembly
• Logistica del progetto
• Introduzione al processore MIPS R2000
• I 32 Registri della cpu MIPS
  • Nomi simbolici dei registri
• Struttura della memoria nel MIPS
• Numerazione delle locazioni di memoria
• Architettura Load e Store
• Direttive all'Assemblatore
• Primi esempi di programmi Assembly (usando il simulatore PCSpim)

Lezione Martedì 16 Maggio 2006

---

• E' stata distribuita la cartina "muta" di un processore con architettura Pipeline
  • descrizione logica-funzionale dei vari componenti del processore rappresentato dalla cartina.
• Pipeline
• Alcuni possibili problemi dovuti all'esecuzione "parallela" di Istruzioni che usano il risultato di quelle precedenti
  • le possibili soluzioni
    • 1) attesa che l'istruzione venga terminata prima di iniziare quella successiva
    • 2) il cambio ove possibile dell'ordine di esecuzione (ad opera del compilatore)
• Ottimizzazioni ad opera del compilatore
  • Esempio di un semplice codice e della relativa ottimizzazione
• Il "problema" dei salti nell'architettura PIPELINE

Lezione Giovedì 18 Maggio 2006

---

Seconda Lezione di Assembly tenuta dal dot. V.Marra

• Set di Istruzioni Mips R2000

• I 3 diversi formati di Istruzioni
  • Tipo R (tipo Registro)
  • Tipo I (Interagisce con la memoria)
  • Tipo J (per i salti)

• Modalità di indirizzamento
  • Assoluto
  • Indiretto
• Le Istruzioni LOAD
• Le Istruzioni STORE
• Varianti di LOAD (li,la)

• Le istruzioni di salto non condizionato(JUMP)
  • Jump , jump on register , jump and link
• salto condizionato (BRANCH)
  • Branch on equal, Branch on not equal, Branch on greater than zero
• Primi esempi di programmi scritti in assembly(con MIPSTER)

Lezione Martedì 23 Maggio 2006

---

• Possibili problemi dell'architettura PIPELINE :
  • Problematiche legate ai salti NON CONDIZIONATI
    • Esempio: un istruzione Jump preceduta da un altra istruzione indipendente
    • Risoluzione usando la tecnica dello slot-delay
    • Risoluzione non ottimizzata inserendo NOP (No OPeration) per evitare il fetch di un istruzione successiva da non eseguire
  • Problematiche legate ai salti CONDIZIONATI
    • problema maggiormente complesso infatti se possiamo anticipare il controllo della condizione rimane il problema di calcolare l'indirizzo a cui saltare!!
  • Alcuni possibili approcci al problema dei salti condizionati
    • UN POSSIBILE APPROCCIO STATICO: I salti indietro vengono sempre previsti come "buoni" (questo tipo di approccio è basato sul fatto che una delle situazioni più frequenti in cui viene seseguito un salto condizionato è l'iterazione)-I salti in avanti vengono sempre previsti come "non buoni"
    • UN POSSIBILE APPROCCIO DINAMICO: Dynamic Branch Prediction
      • la tabella della storia dei salti
      • Questo approccio si bassa sulla storia specifica dei salti( l'idea alla base è che un saldo che abbia avuto successo e probabile che avrà ancora successo , così come un salto che non ha avuto successo è probabile che non lo abbia ancora)
      • L'automa a stati finiti della Dynamic Branch Prediction
• LE NUOVE ISTRUZIONI DI SALTO CONDIZIONATO DELL'ULTRASPARC III
  • Queste Istruzioni nuove hanno un bit che è impostato dal compilatore sulla base della predizione effettuata
• I registri nell'ULTRASPARC III

Lezione Giovedì 25 Maggio 2006

---

Terza ed ultima Lezione di Assembly tenuta dal dot. V.Marra

• la chiamata di procedura
  • Jump non basta : Esempio
  • JAL e JR
  • Il Passaggio dei parametri alla procedura
  • La restituzione dei valori da parte di una procedura
  • Convenzioni MIPS
  • lo STACk e la sua importanza nelle chiamate di procedura
  • L'implementazione MIPS dello stack
    • il registro $sp (stack pointer)
    • Il push -implemantazione mips
    • il pop -implementazione mips
  • Alcuni Esempi
• Le Chiamate di procedura ricorsive
  • Alcuni esempi