Architettura e reti logiche 7
Transcript of Architettura e reti logiche 7
Modulo 1 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Necessità di rappresentare l'informazione
Architetture e reti logiche
Modulo 1 – Realizzazione di una rete logica
Unità didattica 1 – Rappresentazione elettronica dell'informazione
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Cosa è l'informatica
Scienza e tecnologia che si occupa di elaborare INFORmazioni in modo autoMATICO.
Automatica: richiede un sistema capace di trasformare materie prime in prodotti finiti senza intervento diretto dell'uomo.
Informatica: richiede un sistema macchina in grado di manipolare informazioni in modo automatico.
Modulo 1 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Manipolazione automatica
Una "macchina" è un oggetto capace di:• modificare in modo autonomo il proprio stato;• agendo su una o più grandezze fisiche (posizioni
e dimensioni di pezzi meccanici, temperature, ecc.).
Per realizzare una "macchina informatica", serve una grandezza fisica che:
• possa essere modificata in modo automatico;• possa rappresentare concetti astratti (le
informazioni).
Rappresentazione di informazioni
Identificazione dell'informazione che si vuole elaborare: il rappresentato.
Scelta della grandezza fisica: il rappresentante.
Scelta della corrispondenza fra rappresentato e rappresentante.
Modulo 1 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Rappresentato
Può essere qualsiasi informazione che richieda elaborazione automatica.
Esempi di rappresentati:
• la velocità di crociera di un'auto;• la temperatura di un locale;• il tasso di umidità relativa nell'aria;• lo stato (INSERITO/DISINSERITO) del sistema di
allarme di un'abitazione.
Rappresentante
Può essere qualsiasi grandezza fisica il cui comportamento sia noto e modificabile in modo automatico.
Esempi di rappresentanti:
• meccanico: il tachimetro a lancetta dell'auto;• termico: il termometro a mercurio;• chimico: le statuine che cambiano colore e
"prevedono" il tempo;• elettrico: il LED che si accende per segnalare
l'inserimento dell'antifurto di casa.
Modulo 1 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Criteri di scelta del rappresentante
Si vuole costruire una macchina:
• di dimensioni contenute;
• veloce;
• economica da costruire;
• economica da far funzionare.
CRITERI REALIZZATIVI
Perché rappresentanti elettrici
Tensioni e correnti hanno:
• dimensioni contenute: elettroni all'interno di un circuito;
• alta velocità: assenza di parti in movimento;
• bassi costi di realizzazione: materiali comuni;
• bassi costi di esercizio: sufficienti tensioni e correnti piccole.
Modulo 1 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
Perché i circuiti integrati
Grazie alla tecnologia dell'integrazione su silicio:
• dimensioni fisiche ridottissime: frazioni di micron;
• velocità di variazione elevate: frazioni di nanosecondo;
• costi di realizzazione minimi: frazioni di valuta;
• consumi di energia minimi: frazioni di microwatt.
In sintesi...
Informatica e elettronica sono strettamente correlate:
• l'integrazione consente di avere elevati numeri di rappresentanti;
• possiamo rappresentare tante informazioni;
• l'elaborazione automatica delle informazioni diventa economicamente conveniente.
Modulo 1 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 6
Prossimi passi
Dobbiamo decidere quali criteri adottare per rappresentare in modo
elettrico informazioni.
Chiusura
Modulo 1 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Rappresentazione analogica dell'informazione
Architetture e reti logiche
Modulo 1 - Realizzazione di una rete logica
Unità didattica 1 - Rappresentazione elettronica dell'informazione
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Rappresentazione = corrispondenza
Noto il campo di variabilità dell'informazione (rappresentato).
Noto il campo di variabilità della grandezza elettrica (rappresentante).
Definire un CRITERIO che faccia corrispondere ad ogni valore del rappresentato un valore del
rappresentante.
Modulo 1 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Esempio di corrispondenza
Rappresentato - il valore numerico che esprime la temperatura di un locale in gradi centigradi:
• variabile fra Tmin e TMAX
Rappresentante - una tensione elettrica fra due punti di un circuito:
• variabile fra 0 e VMAX
Graficamente
Informazioneda rappresentare(Temperatura)
Grandezza elettrica rappresentante (tensione o Voltaggio)
0
VMAX
Tmin TMAX
Modulo 1 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Rappresentazione analogica
Informazioneda rappresentare(Temperatura)
Grandezza elettrica rappresentante (tensione o Voltaggio)
0
VMAX
Tmin TMAX
Rappresentazione analogica
Corrispondenza BIUNIVOCA fra rappresentato e rappresentante:
• ad ogni valore del rappresentato
• … corrisponde uno e un solo valore del rappresentante
• … e VICEVERSA.
Modulo 1 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Rappresentazione analogica
Informazioneda rappresentare(Temperatura)
Grandezza elettrica rappresentante (tensione o Voltaggio)
0
VMAX
Tmin TMAX0T
0V
Rappresentazione analogica: vantaggi
È una rappresentazione FEDELE:
• anche piccole variazioni del rappresentato si riflettono nel rappresentante.
È una rappresentazione INTUITIVA:
• dal rappresentante si risale immediatamente al rappresentato;
• le variazioni del rappresentante fanno capire immediatamente il comportamento del rappresentato.
Modulo 1 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Rappresentazione analogica: svantaggi
È una rappresentazione VULNERABILE:
• ogni valore del rappresentante è ammissibile;
variazioni della curva di corrispondenza dovute a disturbi, invecchiamento dei
circuiti, ecc. , provocano errori di rappresentazione.
Rappresentazione analogica: svantaggi
Informazioneda rappresentare(Temperatura)
Grandezza elettrica rappresentante (tensione o Voltaggio)
0
VMAX
Tmin TMAX
0V
T0T'0
Modulo 1 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 6
Rappresentazione analogica: svantaggi
È una rappresentazione che aumenta gli ERRORI DI ELABORAZIONE:
• ogni rappresentazione è intrinsecamente affetta da errore di approssimazione;
• operando su rappresentanti approssimati (es. somme, prodotti, ecc.) l'errore di approssimazione aumenta a ogni risultato.
In sintesi...
La rappresentazione analogica:
• fedele e intuitiva;
• introduce tuttavia un errore di approssimazione che la rende poco adatta a elaborazioni -soprattutto se complesse - delle informazioni rappresentate.
Modulo 1 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 7
Chiusura
Modulo 1– U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Rappresentazione digitale dell'informazione
Architetture e reti logiche
Modulo 1 - Realizzazione di una rete logica
Unità didattica 1 - Rappresentazione elettronica dell'informazione
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Idea di base
Per eliminare la vulnerabilità della rappresentazione analogica occorre evitare che qualsiasi valore del rappresentante sia ammissibile.
Scelta di un numero discreto di valori del rappresentante, ciascuno associato a una
CIFRA (in inglese DIGIT).
Modulo 1– U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Rappresentazione digitale
Informazioneda rappresentare(Temperatura)
Grandezza elettrica rappresentante (tensione o Voltaggio)
0
VMAX
Tmin TMAX
2V
1V
0V
Rappresentazione digitale
Corrispondenza UNIVOCA fra rappresentato e rappresentante:
• ad ogni valore del rappresentato
• … corrisponde uno e un solo valore del rappresentante
• … MA NON VICEVERSA! Uno stesso valore di rappresentante è associato a un INTERVALLO di valori del rappresentato.
Modulo 1– U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Rappresentato-rappresentante
Informazioneda rappresentare(Temperatura)
Grandezza elettrica rappresentante (tensione o Voltaggio)
0
VMAX
Tmin TMAX
0V
T0iT fT
Rappresentazione digitale: vantaggi
È una rappresentazione ROBUSTA:
• variazioni del valore del rappresentante dovute a disturbi o invecchiamento dei circuiti vengono riconosciute come ERRORI;
• se le variazioni sono sufficientemente piccole, si può risalire al valore corretto del rappresentante (possibilità di AUTOCORREZIONE).
Modulo 1– U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Rappresentazione digitale: vantaggi
Informazioneda rappresentare(Temperatura)
Grandezza elettrica rappresentante (tensione o Voltaggio)
0
VMAX
Tmin TMAX
0V
T0
V'0
Rappresentazione digitale: vantaggi
È una rappresentazione che ben si presta a ELABORAZIONI ANCHE COMPLESSE:
• l'autocorrezione elimina gli errori di approssimazione.
Modulo 1– U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
Rappresentazione digitale: svantaggi
È una rappresentazione POCO FEDELE:
• variazioni del rappresentato all'interno di un intervallo associato a una cifra del rappresentante non vengono rilevate.
È una rappresentazione POCO INTUITIVA:
• serve interpretare il significato della cifra assunta dal rappresentante.
In sintesi...
La rappresentazione digitale:
• poco fedele e poco intuitiva;
• consente tuttavia l'autocorrezione del valore del rappresentante:- elimina l'errore di approssimazione;
- diventa adatta a elaborazioni anche complesse.
Modulo 1– U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 6
Chiusura
Modulo 1 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 4 – Rappresentazionebinaria dell'informazione
Architetture e reti logiche
Modulo 1 - Realizzazione di una rete logica
Unità didattica 1 - Rappresentazione elettronica dell'informazione
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Idea di base
Rappresentazione digitale robusta e affidabile.
Massimizzazione della robustezza: solo DUE valori del rappresentante, ciascuno associato a una CIFRA BINARIA (o BIT, dall'inglese BINARY
DIGIT).
Particolarmente adatta a elaborazioni anche complesse.
Modulo 1 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 2
Rappresentazione binaria
Informazioneda rappresentare(Temperatura)
Grandezza elettrica rappresentante (tensione o Voltaggio)
0
VMAX
Tmin TMAXTsoglia
Rappresentazione binaria: vantaggi
Rappresentazione ESTREMAMENTE ROBUSTA:
• per confondere le due cifre binarie, disturbo o invecchiamento gravi;
• autocorrezione ancora più semplice (0 o VMAX);• OK per elaborazioni anche complesse.
Rappresentazione ECONOMICA:
• circuiti in stato 0 e VMAX consumano poco;• possono essere più piccoli;• possono essere più numerosi a parità di spazio.
Modulo 1 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 3
Rappresentazione binaria: svantaggi
Rappresentazione TROPPO LIMITATA:
• due soli valori dicono troppo poco.
Serve aumento di accuratezza:
• rapporto UNO-A-MOLTI: rappresentato associato a SEQUENZA DI RAPPRESENTANTI (STRINGA di bit);
• lunghezza stringa legata a accuratezza;• n bit → 2n possibili valori del rappresentato.
In sintesi...
La rappresentazione binaria:
• robusta, affidabile, economica;
• troppo poco espressiva: serve stringa di bit di lunghezza adeguata per rappresentare con la necessaria accuratezza l'informazione.
Modulo 1 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 1 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Codifiche binariedei vari tipi di informazione
Architetture e reti logiche
Modulo 1 - Realizzazione di una rete logica
Unità didattica 2 - Rappresentazione di informazioni con varie quantità di bit
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Informazioni da rappresentare
Vogliamo dare una rappresentazione binaria ai vari modi in cui si presentano le informazioni che ci troviamo a trattare:
• quantità espresse da NUMERI;• descrizioni testuali espresse mediante
CARATTERI (lettere dell'alfabeto, simboli di interpunzione, ecc.);
• immagini costituite da MATRICI BIDIMENSIONALI DI PIXEL ("mosaici" con un certo numero di "tessere": per es. 1280x1024);
• suoni costituiti da FORME D'ONDA che riproducono le variazioni di pressione dell'aria;
• filmati costituiti da SUONI e sequenze di IMMAGINI.
Modulo 1 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Questo è un... iperinsegnamento!
Come in un ipertesto, navighiamo nel corso di laurea online e saltiamo all'insegnamento di FONDAMENTI DI INFORMATICA, dove troviamo le informazioni necessarie per rispondere ai requisiti appena espressi:
Modulo xUnità didattica yLezioni z1, z2, ...
Chiusura
Modulo 1 – UD 3 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 1
Lezione 1 – Postulati dell'algebra booleana
Architetture e reti logiche
Modulo 1 - Realizzazione di una rete logica
Unità didattica 3 - Algebra booleana e sua utilizzabilità
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Algebra booleana
Definita dal matematico inglese George Boolenel 1854.
Nasce per operare su affermazioni che possono assumere solo due valori: VERO o FALSO.
Adatta a trattare grandezze binarie:• 0 o 1;• tensione nulla o tensione positiva;• circuito spento o circuito acceso.
Modulo 1 – UD 3 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 2
Postulato P1
Definita X come (grandezza) variabile dell'algebra booleana:
(P1) X = 0 iff X ? 1(P1')X = 1 iff X ? 0
Questo postulato afferma solo che stiamo trattando grandezze binarie.
Postulato P2
Definito X il valore opposto di quello assunto dalla variabile X (dove X e X sono i due LETTERALI della stessa variabile) :
(P2) if X = 0 then X = 1(P2')if X = 1 then X = 0
Si è definita l'operazione di NEGAZIONE (NOT):X è il NEGATO di X.
Modulo 1 – UD 3 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 3
Postulati P3, P4 e P5
(P3) 0 · 0 = 0
(P4) 1 · 1 = 1
(P5) 1 · 0 = 0 · 1 = 0
Si sono definite le due operazioni di PRODOTTO LOGICO (AND) e di SOMMA LOGICA (OR).
(P3') 1 + 1 = 1
(P4') 0 + 0 = 0
(P5') 0 + 1 = 1 + 0 = 1
Principio di dualità
Ogni postulato Pi dell'algebra booleana ha una seconda versione Pi' che si ottiene sostituendo:
• ogni valore 0 con un valore 1 (e viceversa);• ogni operatore · con un operatore + (e viceversa).
Tutti i teoremi che discendono da questi postulati devono godere della dualità.
Modulo 1 – UD 3 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 4
In sintesi...
Un'algebra per grandezze a due valori.
Consente di operare su grandezze a due valori mediante tre operatori fondamentali:
• NOT (negazione);• AND (prodotto logico);• OR (somma logica).
Gode del principio di dualità: per ogni espressione, ne esiste una duale con:
• scambio tra 0 e 1;• scambio tra prodotti e somme.
Chiusura
Modulo 1 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Teoremidell'algebra booleana
Architetture e reti logiche
Modulo 1 - Realizzazione di una rete logica
Unità didattica 3 - Algebra booleana e sua utilizzabilità
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Teoremi dell'algebra booleana
Relazioni fra variabili booleane e operatori booleani derivati dai postulati.
Permettono di trasformare espressioni booleane.
L'uso di parentesi e la precedenza degli operatori sono gli stessi dell'aritmetica.
Sono quasi tutti dimostrabili per INDUZIONE MATEMATICA PERFETTA (sostituendo tutte le possibili combinazioni dei valori 0 e 1 alle variabili coinvolte).
Modulo 1 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Teoremi a una variabileIdentità(T1) X + 0 = X (T1') X · 1 = X
Elementi nulli(T2) X + 1 = 1 (T2') X · 0 = 0
Idempotenza(T3) X + X = X (T3') X · X = X
Complementi(T5) X + X = 1 (T5') X · X = 0
Involuzione(T4) (X) = X
Teoremi a due variabili
Commutatività(T6) X + Y = Y + X (T6') X · Y = Y · X
Assorbimento(T7) X + X · Y = X (T7') X · (X + Y) = X
Senza nome...(T8) (X + Y) · Y = X · Y(T8') X · Y + Y = X + Y
Modulo 1 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Teoremi a tre variabiliAssociatività(T9) (X + Y) + Z = X + (Y + Z) = X + Y + Z(T9') (X · Y) · Z = X · (Y · Z) = X · Y · Z
Distributività(T10) X · Y + X · Z = X · (Y + Z)(T10') (X + Y) · (X + Z) = X + Y · Z
Consenso
(T11) (X + Y) · (X + Z) · (Y + Z) = (X + Y) · (X + Z)
(T11') X · Y + X · Z + Y · Z = X · Y + X · Z
Un altro senza nome...
(T12) (X + Y) · (X + Z) = X · Z + X · Y
Teoremi a n variabili
De Morgan
(T13) (X1 + X2 + ... + Xn) = X1 · X2 · ... · Xn
(T13') (X1 · X2 · ... · Xn) = X1 + X2 + ... + Xn
De Morgan generalizzato
(T14) f (X1 , X2 , ... , Xn , + , ·) == f (X1 , X2 , ... , Xn , · , +)
Espansione
(T15) f (X1 , X2 , ... , Xn) == X1 · f (1 , X2 , ... , Xn) + X1 · f (0 , X2 , ... , Xn)
(T15') f (X1 , X2 , ... , Xn) ==[X1+ f (0 , X2 , ... , Xn)] · [X1 + f (1 , X2 ,... , Xn)]
Modulo 1 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Importanza di De Morgan
Consente di trasformare prodotti logici in somme e viceversa utilizzando i negatori.
Utilissimo se la tecnologia elettronica scelta facilita la realizzazione di sommatori logici piuttosto che di moltiplicatori logici, o viceversa.
In sintesi...
Numerosi teoremi per la manipolazione delle espressioni logiche:
• strumenti per operare su grandezze binarie;
• strumenti per modificare le regole di operazione sulle grandezze binarie per ottenere gli stessi risultati con espressioni diverse (più semplici).
Modulo 1 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Chiusura
Modulo 1 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Aritmetica conl'algebra booleana
Architetture e reti logiche
Modulo 1 - Realizzazione di una rete logica
Unità didattica 3 - Algebra booleana e sua utilizzabilità
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Serve davvero l'algebra booleana?
Come detto, è un'algebra per operare su grandezze binarie.
Opera mediante i tre operatori: NOT, AND, OR.
Può essere utilizzata per elaborare informazioni più complesse?
• Un esempio: la somma aritmetica di due numeri interi A e B codificati ciascuno con 1 bit.
• Un secondo esempio: la somma aritmetica di due numeri interi A e B codificati ciascuno con 2 bit.
Modulo 1 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Somma di due numeri a 1 bit
A e B sono due numeri interi a 1 bit:• ciascuno dei due numeri può valere 0 oppure 1;• se entrambi i numeri valgono 0, la loro somma
vale 0;• se uno solo dei due numeri vale 1, la loro
somma vale 1;• se entrambi i numeri valgono 1, la loro somma
vale 2, che non è rappresentabile con un solo bit: si genera un riporto.
S è il bit di somma.R è il bit di riporto.
Somma di due numeri a 1 bit
Ecco la TABELLA DELLE VERITÀ della rete da progettare:
1011
0101
0110
0000
RSBA
Modulo 1 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Somma di due numeri a 1 bit
La realizzazione del riporto è immediata:R = A · B
La realizzazione della somma un po’ meno:S = (A · B) + (A · B)
Ho le espressioni logiche per costruire un circuito sommatore a 1 bit (HALF ADDER).
Circuito HALF ADDER
A B
S
R HA
Modulo 1 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Somma di due numeri a 2 bit
A e B sono due numeri interi a 2 bit:• ciascuno dei numeri può valere 0, 1, 2 o 3;• A0 e B0 sono i 2 bit meno significativi;• A1 e B1 sono i 2 bit più significativi.
Il circuito Half Adder visto prima ci consente di sommare A0 e B0 generando il bit meno significativo della somma S0 e il riporto R0.
Serve un circuito in grado di sommare A1 e B1tenendo conto anche dell'eventuale riporto R0per generare il bit più significativo della somma S1 e il riporto finale R1.
Somma di due numeri a 2 bit
Ecco la TABELLA DELLE VERITÀ della rete da progettare:
11111
10011
10101
01001
0
1
1
0
S1
1110
0010
0100
0000
R1R0B1A1
Modulo 1 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
Somma di due numeri a 2 bit
Ecco l'espressione per calcolare il riporto R1:R1 = A1B1 + A1R0 + B1R0
Ecco l'espressione per calcolare la somma S1:S1 = A1B1R0 + A1B1R0 + A1B1R0 + A1B1R0
Ho le espressioni logiche per costruire un circuito sommatore che tiene conto del riporto
precedente (FULL ADDER).
Circuito FULL ADDER
FAR
S
A B
R
1 1
0
1
1
Modulo 1 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 6
Circuito per la somma a 2 bit
HA
S
A B
FAR
S1
1
1 1A B
R0
0 0
0
In sintesi...
Con espressioni booleane, si riesce a realizzare circuiti in grado di svolgere operazioni di altro tipo (come operazioni aritmetiche, su informazioni numeriche).
Circuiti descritti con le regole dell'algebra booleana possono svolgere elaborazioni su
informazioni di tipo qualsiasi.
Modulo 1 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 7
Chiusura
Modulo 1 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 4 – Porte logiche
Architetture e reti logiche
Modulo 1 - Realizzazione di una rete logica
Unità didattica 3 - Algebra booleana e sua utilizzabilità
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Operatori booleani su silicio
L'algebra booleana è un valido strumento per la gestione di variabili binarie.
Ma è solo uno strumento metodologico?
No: l'elettronica consente di realizzare nei circuiti integrati gli operatori fondamentali dell'algebra booleana.
Modulo 1 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 2
Negatore bipolare
I
U
RI
UR
CC
C
EB
Porta NOT
OUT
OUT
Modulo 1 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 3
Porta AND
OUT
Porta OR
OUT
Modulo 1 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 4
Porta NAND
OUT
Porta NOR
OUT
Modulo 1 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 5
In sintesi...
La tecnologia elettronica consente di realizzare in modo compatto ed efficiente gli operatori dell'algebra booleana.
Mediante tali operatori, sono possibili elaborazioni di informazioni qualsiasi.
BINGO! Abbiamo tutti gli ingredienti per realizzare la macchina informatica.
Chiusura
Modulo 2 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architettura e reti logiche 1
Lezione 1 – Analisi di una rete combinatoria
Architetture e reti logiche
Modulo 2 – Progettazione di una rete combinatoria
Unità didattica 1 – Sintesi di una rete combinatoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Esempio di rete combinatoria
w
xy
z
f
Descrizione strutturale
Modulo 2 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architettura e reti logiche 2
Esempio di rete combinatoria
w
xy
z
f
Descrizione comportamentale
Tabella delle verità
1111115
1011114
1101113
0001112
0110111
0010110
110019
000018
011107
001106
110105
000104
011003
001002
110001
000000
fzyxw#
Modulo 2 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architettura e reti logiche 3
In sintesi...
Analisi della rete combinatoria:• dalla struttura,• al comportamento.
Interessa passare:• dal comportamento,• alla struttura.
Dobbiamo trovare strumenti che ci consentanodi effettuare una sintesi.
Chiusura
Modulo 2 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architettura e reti logiche 1
Lezione 2 – Sintesi di una rete combinatoria: prima forma canonica
Architetture e reti logiche
Modulo 2 – Progettazione di una rete combinatoria
Unità didattica 1 – Sintesi di una rete combinatoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Punto della situazione
Abbiamo analizzato come si comporta una rete combinatoria:
• dalla sua descrizione strutturale(schema circuitale o espressione logica);
• alla sua descrizione comportamentale(tabella delle verità).
Dobbiamo trovare il modo per sintetizzare (costruire) una rete logica:
• dalla sua descrizione comportamentale;• alla sua descrizione strutturale.
Modulo 2 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architettura e reti logiche 2
Prima tabella delle verità
0111115
0011114
0101113
0001112
1110111
0010110
010019
000018
011107
001106
010105
000104
011003
001002
010001
000000
fzyxw#
Sintesi della prima rete
Modulo 2 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architettura e reti logiche 3
Seconda tabella delle verità
0111115
0011114
0101113
0001112
1110111
0010110
010019
000018
011107
101106
010105
000104
011003
001002
010001
000000
fzyxw#
Sintesi della seconda rete
Modulo 2 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architettura e reti logiche 4
Mintermine
Prodotto logico associato a una configurazione degli ingressi.Gode della proprietà di valere 1 quando gli ingressi assumono la configurazione associata, e 0 in tutti gli altri casi.
Cita tutte le variabili di ingresso:• diritte se compaiono come UNI nella
configurazione associata;• negate se compaiono come ZERI nella
configurazione associata.
In sintesi...
Abbiamo definito la prima forma canonica di sintesi delle reti combinatorie:
• sintesi in forma SP (Sum of Products);
• una porta AND per ogni mintermine associato a un UNO della funzione;
• una porta OR finale che effettua la somma di tutti i mintermini associati a UNI della funzione.
Modulo 2 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architettura e reti logiche 5
Chiusura
Modulo 2 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architettura e reti logiche 1
Lezione 3 – Sintesi di una rete combinatoria: seconda forma
canonica
Architetture e reti logiche
Modulo 2 – Progettazione di una rete combinatoria
Unità didattica 1 – Sintesi di una rete combinatoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Prima tabella delle verità
1111115
1011114
1101113
1001112
1110111
1010110
110019
100018
111107
101106
110105
100104
111003
001002
110001
100000
fzyxw#
Modulo 2 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architettura e reti logiche 2
Sintesi della prima rete
Seconda tabella delle verità
1111115
1011114
1101113
1001112
1110111
1010110
110019
000018
111107
101106
110105
100104
111003
001002
110001
100000
fzyxw#
Modulo 2 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architettura e reti logiche 3
Sintesi della seconda rete
Maxtermine
Somma logica associata a una configurazione degli ingressi.Gode della proprietà di valere 0 quando gli ingressi assumono la configurazione associata, e 1 in tutti gli altri casi.
Cita tutte le variabili di ingresso:• diritte se compaiono come ZERI nella
configurazione associata;• negate se compaiono come UNI nella
configurazione associata.
Modulo 2 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architettura e reti logiche 4
In sintesi...
Abbiamo definito la seconda forma canonica di sintesi delle reti combinatorie:
• sintesi in forma PS (Product of Sums);
• una porta OR per ogni maxtermine associato a uno ZERO della funzione;
• una porta AND finale che effettua il prodotto di tutti i maxtermini associati a ZERI della funzione.
Chiusura
Modulo 2 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 1
Lezione 4 – Complessità di una rete combinatoria
Architetture e reti logiche
Modulo 2 – Progettazione di una rete combinatoria
Unità didattica 1 – Sintesi di una rete combinatoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Punto della situazione
Abbiamo visto due modi di progettare reti combinatorie:
• prima forma canonica;• seconda forma canonica.
Il numero di porte AND (OR) necessarie dipende dal numero di UNI (ZERI) presenti nella tabella delle verità.
Il numero di ingressi alla porta OR (AND) finale dipende a sua volta dal numero di UNI (ZERI) presenti nella tabella delle verità.
Modulo 2 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 2
Elementi di misura della complessità
N° di livelli di porte logiche da attraversare:• tiene conto del ritardo di commutazione delle
porte.N° di porte AND e OR (trascuriamo i NOT):
• tiene conto della complessità circuitale totale.N° totale di ingressi alle porte AND e OR:
• tiene conto della complessità di realizzazione della singola porta.
Notazione risultante: x L y G z I
w
xy
z
f
Primo esempio
Modulo 2 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 3
Secondo esempio
In sintesi...
Una notazione molto sintetica, che però consente di confrontare rapidamente diverse reti combinatorie:
• in termini di tempo di lavoro (livelli di porte logiche da attraversare);
• in termini di complessità realizzativa (numero e complessità delle porte logiche necessarie).
Modulo 2 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 4
Chiusura
Modulo 2 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Differenti complessità di una rete combinatoria
Architetture e reti logiche
Modulo 2 - Progettazione di una rete combinatoria
Unità didattica 2 - Ottimizzazione di una rete combinatoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Punto della situazione
Nella precedente unità didattica abbiamo:• effettuato l'analisi del comportamento di una
rete combinatoria;• individuato una prima forma canonica per la
sintesi di una rete combinatoria, basata sulla somma di mintermini (forma SP: Sum of Products);
• individuato una seconda forma canonica per la sintesi di una rete combinatoria, basata sul prodotto di maxtermini (forma PS: Product of Sums).
Confrontiamo i risultati.
Modulo 2 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Tabella delle verità
1111115
1011114
1101113
0001112
0110111
0010110
110019
000018
011107
001106
110105
000104
011003
001002
110001
000000
fzyxw#
• 6 uni
• 10 zeri
Altre possibili notazioni
Indica le posizioni degli UNI della funzione, e suggerisce la sintesi come Somma di Prodotti(da cui il simbolo di Sommatoria)
Indica le posizioni degli ZERI della funzione, e suggerisce la sintesi come Prodotto di Somme(da cui il simbolo di Produttoria)
∑1
(1,5,9,13,14,15)
∏0
(0,2,3,4,6,7,8,10,11,12)
Modulo 2 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Tre possibili reti combinatorie
Rete proposta per l'analisi:• trascurando i negatori, 3 porte AND a 2 ingressi, 1
porta OR a 3 ingressi, 1 porta OR a 2 ingressi;• complessità: 3L5G11I.
Prima forma canonica:• 6 mintermini (per i 6 uni), cioè 6 porte AND a 4
ingressi, più 1 porta OR a 6 ingressi per la Somma;• complessità: 2L7G30I.
Seconda forma canonica:• 10 maxtermini (per i 10 zeri), cioè 10 porte OR a 4
ingressi, più 1 porta AND a 10 ingressi per il Prodotto;
• complessità: 2L11G50I.
Prima possibile ottimizzazione:i teoremi dell'algebra di Boole
Nella dispensa della lezione, si vede come sia possibile passare dalla prima forma canonica SP alla forma a 3 livelli usata per l'analisi.
• Uso non certo intuitivo dei vari teoremi dell'algebra di Boole.
• Serve esperienza e intuito.
• Il risultato finale non è garantito (procedimento NON univoco).
Modulo 2 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Seconda possibile ottimizzazione:gli implicanti
Usiamo solo i teoremi di distributività, dei complementi e dell'elemento nullo.Raccogliamo a fattor comune tre variabili fra coppie di mintermini che differiscono solo per la quarta (diritta o negata).
Possiamo ripetere il procedimento se dopo i raccoglimenti fra coppie di minterminiotteniamo prodotti che differiscono ancora per una sola variabile (diritta o negata).
Le reti ottenute sono sempre reti a DUE livelli.Nella dispensa, arriviamo a 2L3G7I.
Implicante
Prodotto logico.• Deriva da un insieme di mintermini di
cardinalità 2p (1, 2, 4, 8, ...).• I mintermini dell'insieme sono caratterizzati dal
fatto di essere associati a configurazioni degli ingressi nelle quali:
– alcuni ingressi hanno sempre lo stesso valore (0 o 1);
– gli altri ingressi assumono tutte le possibili combinazioni di 0 e 1.
• Il prodotto logico cita solo le variabili di ingresso che non cambiano valore, negate se il valore è0, diritte se il valore è 1.
• Diminuisce sia il numero di porte, sia il numero di ingressi per porta.
Modulo 2 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
Terza possibile ottimizzazione:gli implicati
Usiamo solo i teoremi di distributività, dei complementi e dell'elemento nullo.Raccogliamo ad addendo comune tre variabili fra coppie di maxtermini che differiscono solo per la quarta (diritta o negata).
Possiamo ripetere il procedimento se dopo i raccoglimenti fra coppie di maxterminiotteniamo somme che differiscono ancora per una sola variabile (diritta o negata).
Le reti ottenute sono sempre reti a DUE livelli.
Implicato
Somma logica.• Deriva da un insieme di maxtermini di
cardinalità 2p (1, 2, 4, 8, ...).• I maxtermini dell'insieme sono caratterizzati dal
fatto di essere associati a configurazioni degli ingressi nelle quali:
– alcuni ingressi hanno sempre lo stesso valore (0 o 1);
– gli altri ingressi assumono tutte le possibili combinazioni di 0 e 1.
• La somma logica cita solo le variabili di ingresso che non cambiano valore, diritte se il valore è0, negate se il valore è 1.
• Diminuisce sia il numero di porte, sia il numero di ingressi per porta.
Modulo 2 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 6
In sintesi...
Limitandoci a costruire reti combinatorie a due livelli, abbiamo due metodi per ridurre sia il numero delle porte sia il numero degli ingressi:
• sintesi SP mediante il ricorso agli implicanti;
• sintesi PS mediante il ricorso agli implicati.
Serve un metodo per trovare gli implicanti o gli implicati più "efficaci", cioè quelli che "riassumono" in sé il maggior numero, rispettivamente, di mintermini e di maxtermini.
Chiusura
Modulo 2 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Ricerca di implicanti e implicati
Architetture e reti logiche
Modulo 2 - Progettazione di una rete combinatoria
Unità didattica 2 - Ottimizzazione di una rete combinatoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Punto della situazione
Nella precedente lezione abbiamo visto l'importanza e l'utilità degli implicanti e degli implicati.Implicanti (implicati) riuniscono insiemi di mintermini (maxtermini) associati a configurazioni di ingresso con parti comuni e parti variabili.Serve un metodo di:
• identificazione degli implicanti (implicati) di massimo grado, quindi più efficaci;
• identificazione dell'insieme minimo di implicanti (implicati) necessari per realizzare la funzione richiesta.
Modulo 2 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Rappresentazione geometricadei numeri binari: gli n-cubi
0- cubo
cubo1-0 1
00 01
10 11
cubo2-
100 101
110 111
001000
010 011
3- cubo0010
0000
0011
0110 0111
0001
0100 0101
1000
1100 1101
1111
10111010
1001
1110
4- cubo
Caratteristiche dell'n-cubo
Definiamo:• Distanza di Hamming = numero di bit differenti
fra due configurazioni (stringhe) di bit.Ogni vertice dell'n-cubo è adiacente (cioèconnesso mediante un segmento) a n altri vertici, associati a configurazioni degli ingressi a distanza di Hamming unitaria dalla configurazione associata al vertice di partenza:
• se ai vertici di un segmento ci sono due UNI (ZERI) della funzione, è possibile un raccoglimento a fattore (addendo) comune fra i due mintermini (maxtermini) associati a tali UNI (ZERI).
Modulo 2 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Uso dell'n-cubo
0010
0000
0011
0110 0111
0001
0100 0101
1000
1100 1101
1111
10111010
1001
1110
• Ogni p-sottocuboassociato a UNI della funzione indica un possibile implicante.
• Nella funzione di esempio, esistono 6 implicanti di ordine 1(associati a 1-cubi, cioèa segmenti).
• Nella funzione di esempio, esiste 1 implicante di ordine 2 (associato a un 2-cubo, cioè a un quadrato).
Tipi di implicantiIl ricorso agli implicanti è tanto più efficace quanto maggiore è il numero di mintermini"riassunti" nell'implicante (cioè quanto più alto è il grado p dell'implicante).Definiamo:
• Implicante - Prodotto logico associato a unp-sottocubo di UNI della funzione.
• Implicante primo - Un implicante associato a un p-sottocubo di UNI della funzione che non ècontenuto in nessun p-sottocubo di UNI della funzione di ordine superiore.
• Implicante essenziale - Un implicante primo che deve essere utilizzato nella sintesi perchéalmeno uno degli UNI della funzione ad esso associati è coperto solo da tale implicante.
Modulo 2 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Tipi di implicanti
0010
0000
0011
0110 0111
0001
0100 0101
1000
1100 1101
1111
10111010
1001
1110
Tipi di implicatiIl ricorso agli implicati è tanto più efficace quanto maggiore è il numero di maxtermini"riassunti" nell'implicato (cioè quanto più alto èil grado p dell'implicato).Definiamo:
• Implicato - Somma logica associata a unp-sottocubo di ZERI della funzione.
• Implicato primo - Un implicato associato a un p-sottocubo di ZERI della funzione che non ècontenuto in nessun p-sottocubo di ZERI della funzione di ordine superiore.
• Implicato essenziale - Un implicato primo che deve essere utilizzato nella sintesi perché almeno uno degli ZERI della funzione ad esso associati ècoperto solo da tale implicato.
Modulo 2 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
In sintesi...
La rappresentazione geometrica dei numeri binari consente di individuare in modo grafico la presenza di:
• implicanti (p-sottocubi associati a UNI della funzione);
• implicati (p-sottocubi associati a ZERI della funzione)
La sintesi ottima si fa:• identificando gli implicanti/ti primi;• sintetizzando gli implicanti/ti essenziali;• coprendo gli UNI/ZERI eventualmente rimasti con
implicanti/ti primi non essenziali.
Chiusura
Modulo 2 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Mappe di Karnaugh
Architetture e reti logiche
Modulo 2 - Progettazione di una rete combinatoria
Unità didattica 2 - Ottimizzazione di una rete combinatoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Mappe di Karnaugh
Rappresentazione planare di n-cubi(più facile da gestire).
Ricordando che:• Distanza di Hamming = numero di bit differenti
fra due configurazioni (stringhe) di bit.
Ogni casella dell'n-cubo è adiacente a n caselle, associate a configurazioni degli ingressi a distanza di Hamming unitaria dalla configurazione associata alla casella di partenza.
Modulo 2 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Mappe di Karnaugh
10119810
1415131211
675401
231000
10110100wx
yz
321
100
10y
z
67541
23100
10110100x
yz
2-cubo
4-cubo
3-cubo
Caratteristiche delle mappe di Karnaugh
Le mappe di Karnaugh sono:• "strutture sferiche svolte sul piano";• le caselle dei bordi verticali sinistro e destro sono
fra loro adiacenti;• le caselle dei bordi orizzontali superiore e
inferiore sono fra loro adiacenti.
Attenzione alla numerazione delle caselle!• Per garantire distanza di Hamming unitaria fra
caselle adiacenti, non seguono l'ordine naturale di numerazione.
Modulo 2 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Uso delle mappe di Karnaugh
00101
01100
10110100x
yz
10011
10110
10110100x
yz
Uso delle mappe di Karnaugh
000110
011111
011101
010100
10110100wx
yz
100110
010011
001101
100100
10110100wx
yz
Modulo 2 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Mappe di Karnaugh a 5 variabili
000010
001011
001001
000000
10110100wx
yz
100010
101011
001001
000000
10110100wx
yz
v = 0 v = 1
Mappe di Karnaugh a 6 variabili
000010
001011
001001
110000
10110100wx
yz
100010
101011
001001
110000
10110100wx
yz
uv = 00 uv = 01
000010
001011
001001
000000
10110100wx
yz
100010
101011
001001
000000
10110100wx
yz
uv = 10 uv = 11
Modulo 2 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
In sintesi...
Le mappe di Karnaugh forniscono un supporto per l'identificazione degli implicanti (implicati) primi ed essenziali.
Sono facilmente utilizzabili fino a 4 variabili di ingresso, meno facilmente utilizzabili per 5 o 6 variabili di ingresso, inutilizzabili per reti piùcomplesse.
Esistono strumenti per sintetizzare reti piùcomplesse (metodo tabellare di QuineMcCluskey) non fondamentali per il nostro insegnamento.
Chiusura
Modulo 2 – U.D. 2 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 4 – Reti combinatorie non completamente specificate
Architetture e reti logiche
Modulo 2 - Progettazione di una rete combinatoria
Unità didattica 2 - Ottimizzazione di una rete combinatoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Reti non completamente specificate
Non sempre è previsto che tutte le 2n possibili configurazioni di n ingressi possano presentarsi a una rete combinatoria.Ad alcune configurazioni di ingresso, sono associate indifferenze nel senso che a chi "compra" la rete è indifferente cosa faccia la rete stessa in corrispondenza di tali configurazioni.
Un esempio:il trascodificatoreda BCD a 7-segmenti.
Modulo 2 – U.D. 2 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 2
Tabella delle verità del trascodificatore
×××××××111115
×××××××011114
×××××××101113
×××××××001112
×××××××110111
×××××××010110
110011110019
111111100018
000011111107
111110101106
110110110105
110011000104
100111111003
101101101002
000011010001
011111100000
gfedcbazyxw#
Mappa di Karnaugh del segmento a
××1110
××××11
111001
110100
10110100wx
yz
Sintesi SP
Sintesi PS
Sono reti diverse!
f (w,x,y,z) = ∑1
(0,2,3,5,6,7,8,9) +
∑×
(10,11,12,13,14,15)
Modulo 2 – U.D. 2 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 3
In sintesi...
Nel caso di reti non completamente specificate, si possono forzare liberamente a 0 o 1 le indifferenze, per aumentare le dimensioni e/o ridurre il numero di implicanti/implicati.Le due sintesi SP e PS non hanno più lo stesso comportamento: per configurazioni di ingresso associate a indifferenze, possono dare uscite differenti in base a come le indifferenze stesse sono state forzate.La rete sintetizzata NON CONTIENE PIÙINDIFFERENZE: a ogni configurazione di ingresso corrisponde una ben precisa uscita.
Chiusura
Modulo 2 – U.D. 2 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 5 – Reti combinatorie a piùuscite
Architetture e reti logiche
Modulo 2 - Progettazione di una rete combinatoria
Unità didattica 2 - Ottimizzazione di una rete combinatoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Reti a più uscite
Molto spesso, le specifiche di progetto di una rete combinatoria mettono in relazione un certo numero di ingressi con un numero maggiore di 1 di uscite funzioni di tali ingressi.
• Esempio del trascodificatore BCD 7-segmenti4 ingressi: w, x, y, z7 uscite: a, b, c, d, e, f, g
Si può procedere a una sintesi separata di ciascuna uscita come funzione autonoma degli ingressi.
Ma è la sintesi ottima?
Modulo 2 – U.D. 2 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 2
Primo esempio
1100101001
0100001100
10110100x10110100x
yzf2yzf1
f1(x,y,z) = ∑1
(1,3,7) f2(x,y,z) = ∑1
(3,6,7)
Realizzazione ottimizzata
Modulo 2 – U.D. 2 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 3
Secondo esempio
1100101001
1000001100
10110100x10110100x
yzf2yzf1
f1(x,y,z) = ∑1
(1,3,7) f2(x,y,z) = ∑1
(2,6,7)
Realizzazione ottimizzata
Modulo 2 – U.D. 2 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 4
Implicante primo di più uscite
L'implicante xyz è un implicante primo della funzionef1 ⋅ f2
Si evidenzia nella mappa di Karnaugh della funzione prodotto:
Nel caso di sintesi PS, servirebbe la mappa di Karnaughdella funzione f1 + f2
01001
00000
10110100x
yzf1 ⋅f2
In sintesi...
Nel caso di reti a più uscite, serve considerare anche gli implicanti primi di tutti i possibili prodotti delle funzioni di ciascuna uscita.
• Con tre uscite, serve dunque considerare i prodotti:
– f1⋅f2
– f1⋅f3
– f2⋅f3
– f1⋅f2⋅f3
• In quanto implicanti comuni a più di una uscita, potrebbero portare a una sintesi migliore.
Con le mappe di Karnaugh risulta complesso.
Modulo 2 – U.D. 2 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 5
Chiusura
Modulo 2 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Cosa sono le alee
Architetture e reti logiche
Modulo 2 - Progettazione di una rete combinatoria
Unità didattica 3 - Errori di comportamento logico:le alee
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Alea (hazard)
Malfunzionamento transitorio dovuto ai ritardi non nulli di commutazione delle porte logiche.Primo tipo di alea:
• alea statica - l'uscita non dovrebbe cambiare, ma per breve tempo assume valore opposto a quello corretto.
– Alea statica di tipo 0(l'uscita dovrebbe rimanere 0).
– Alea statica di tipo 1(l'uscita dovrebbe rimanere 1).
Modulo 2 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Alea (hazard)
Secondo tipo di alea:• alea dinamica - l'uscita dovrebbe cambiare, ma
dopo il primo cambiamento ritorna al valore iniziale per poi assestarsi definitivamente sul valore corretto.
– Alea dinamica ascendente(l'uscita dovrebbe passaredirettamente da 0 a 1).
– Alea dinamica discendente(l'uscita dovrebbe passaredirettamente da 1 a 0).
Esempio di alea statica di tipo 1
Espressione logica
Schema circuitale
10001
11100
10110100x
yz
Modulo 2 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
x01
1y0
1z0
1xz0
1yz0
1f0
tempo
Funzionamento in modo fondamentale
Facciamo variare un solo ingresso alla volta:• ci muoviamo fra caselle adiacenti sulla mappa
di Karnaugh (esempio: da 011 a 010).Diagramma temporale:
Perché si verifica l'alea statica di tipo 1
Nell'esempio, si passa da un UNO della funzione a un UNO adiacente, ma non coperto dal medesimo implicante:
• per questo motivo, l'implicante da cui si esce deve spegnersi (la sua uscita deve passare a 0) e l'implicante in cui si entra deve accendersi (la sua uscita deve passare a 1);
• se il secondo implicante è più lento del primo, per un certo tempo ho tutti 0 davanti alla porta OR.
Nel caso di sintesi PS, avrei alee statiche di tipo 0 passando fra ZERI adiacenti non coperti dal medesimo implicato.
Modulo 2 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
A causa dei ritardi di commutazione, posso avere malfunzionamenti transitori anche in caso di funzionamento in modo fondamentale (quindi variando un solo ingresso alla volta).
Serve capire dove possono verificarsi alee e di che tipo, e come sintetizzare una rete priva di alee.
Chiusura
Modulo 2 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Come identificare ed eliminare le alee
Architetture e reti logiche
Modulo 2 - Progettazione di una rete combinatoria
Unità didattica 3 - Errori di comportamento logico:le alee
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Identificazione delle alee
Partendo dalla generica espressione logica della rete a n livelli, ci portiamo a una forma SP a 2 livelli.
• Utilizzando solo i teoremi di:– associatività;
– distributività;
– De Morgan.
• Non facciamo uso in particolare dei teoremi di:– Complemento;
– Assorbimento.
Modulo 2 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Esempio
Partiamo da una generica espressione:
Ci portiamo alla forma a 2 livelli:
Identifichiamo implicanti e termini spuri:
Comportamento del termine spurio
Circuito equivalente al termine spurio:
Comportamento nel tempo del termine spurio:
Modulo 2 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Mappa di Karnaugh
Riportiamo gli implicanti sulla mappa:
Abbiamo identificato le alee statiche di tipo 1.
10
11
01
00
10110100wx
yz
Mappa di Karnaugh
Consideriamo il termine spurio:
Abbiamo identificato le alee statiche di tipo 0 e le alee dinamiche.
010010
010011
110001
000000
10110100wx
yz
Modulo 2 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Eliminazione delle alee - forma SP
In una sintesi a 2 livelli di tipo SP (nella quale non si introducono termini spuri) le uniche alee possibili sono alee statiche di tipo 1, presenti fra UNI adiacenti non coperti dal medesimo implicante (non ci sono né alee statiche di tipo 0, né alee dinamiche).
Effettuiamo una sintesi ridondante, aggiungendo altri implicanti primi che evitino il verificarsi della clausola sopra citata.
Esempio di eliminazione di alee
10001
11100
10110100x
yz
100110
001111
001101
100100
10110100wx
yz
Modulo 2 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Eliminazione delle alee - forma PS
In una sintesi a 2 livelli di tipo PS (nella quale non si introducono termini spuri) le uniche alee possibili sono alee statiche di tipo 0, presenti fra ZERI adiacenti non coperti dal medesimo implicato (non ci sono né alee statiche di tipo 1, né alee dinamiche).
Effettuiamo una sintesi ridondante, aggiungendo altri implicati primi che evitino il verificarsi della clausola sopra citata.
In sintesi...
L'identificazione delle alee avviene riportandosi a una forma a 2 livelli di tipo SP, che può contenere termini spuri nei quali una variabile compare sia diritta sia negata.I normali implicanti indicano la possibile presenza di alee statiche di tipo 1.I termini spuri indicano la possibile presenza di alee statiche di tipo 0 e di alee dinamiche.Per eliminare le alee, si ricorre a sintesi ridondanti, che evitino UNI (ZERI) adiacenti non coperti dal medesimo implicante (implicato)
Modulo 2 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 6
Chiusura
Modulo 3 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Bistabile SR
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 1 - Bistabili e relative tabelle di eccitazione
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Bistabile SR
S
R
y
y
Modulo 3 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Diagramma temporale
y 01
1y 0
1R 0
1S0
tempo
Può trovarsi in stato stabile con due possibili configurazioni di uscita:
BISTABILE
Eccitazione del bistabile
In base allo stato presente del bistabile:• l'uscita y attuale.
In base allo stato prossimo del bistabile:• l'uscita Y che voglio far assumere al bistabile.
Come devo eccitare il bistabile:• quali configurazioni degli ingressi S e R devo
presentargli.
Modulo 3 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Tabella di eccitazione del bistabile SR
0×11
1001
0110
×000
RSYy
Schema elettrico del bistabile SR
S
R
y
y
Modulo 3 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
Porte logiche connesse con collegamenti ciclici (retroazioni) danno luogo a un comportamento non combinatorio:
• l'uscita della rete logica dipende dalla sequenza delle configurazioni di ingresso ricevute nel recente passato, e non solo dalla configurazione di ingresso attualmente presente;
• l'uscita dipende quindi dalla "storia" delle configurazioni di ingresso, non dalla "cronaca";
• la rete è in grado di tenere memoria di tale storia.
Parliamo di reti sequenziali.
Chiusura
Modulo 3 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Bistabili trasparenti (latch)
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 1 - Bistabili e relative tabelle di eccitazione
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Bistabile SRC
Bistabile SR Controlled:• con segnale di Controllo (o di Clock).
• Se C=1 si comporta come il bistabile SR.• Se C=0 non risente delle variazioni di ingresso.
Modulo 3 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Schema elettrico del bistabile SRC
S
R
y
y
C
Bistabile D
Bistabile Data con segnale di Controllo:• capace di memorizzare un dato da un bit.
Modulo 3 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Tabella di eccitazione del bistabile D
111
001
110
000
DYy
Stato prossimo ed eccitazione coincidono.
Schema elettrico del bistabile D
y
y
D
C
Modulo 3 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Trasparenza dei bistabili
Quando il bistabile è abilitato, ogni variazione degli ingressi si ripercuote sulle uscite, dopo il tempo necessario alle porte logiche per commutare.
• Il bistabile si adegua prontamente alle variazioni degli ingressi.
• Le uscite risentono di ogni variazione degli ingressi, e ne propagano le conseguenze.
Il bistabile è trasparente: non filtra in alcun modo eventuali variazioni spurie degli ingressi.
Chiamiamo questi bistabili LATCH.
In sintesi...
Abbiamo a disposizione diversi elementi in grado di tenere memoria della sequenza di ingressi.
Sono bistabili trasparenti (o LATCH): quando sono abilitati (Clock attivo) non filtrano in alcun modo eventuali variazioni degli ingressi.
In alcuni casi potrebbe essere utile un disaccoppiamento fra ingressi e uscite.
Modulo 3 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Chiusura
Modulo 3 – U.D. 1 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 1
Lezione 3 – Bistabili non trasparenti (flip-flop)
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 1 - Bistabili e relative tabelle di eccitazione
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Configurazione Master-Slave
2 Latch in cascata, con segnali di controllo in controfase:
• Se C=1 si attiva il Master ma lo Slave ècongelato.
• Se C=0 il Master si disattiva mentre lo Slave adegua le uscite finali.
Modulo 3 – U.D. 1 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 2
Bistabile NON trasparente
Le uscite non risentono immediatamente di variazioni degli ingressi, ma solo al semiperiodo successivo del segnale di Clock.
Eventuali variazioni spurie degli ingressi non influiscono sulle uscite: solo i valori staticizzatidal Master vengono propagati dallo Slave.
Chiamiamo questi bistabili FLIP-FLOP.
Schema elettrico del flip-flop SR
S
R
y
y
C
Modulo 3 – U.D. 1 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 3
Schema elettrico del flip flop D
y
y
D
C
Flip-flop JK
Flip-flop SR retroazionato:
• Se almeno uno dei due ingressi J e K vale 0, si comporta come il flip-flop SR (J=S, K=R).
• Se entrambi J e K valgono 1, commuta il proprio stato.
Modulo 3 – U.D. 1 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 4
Tabella di eccitazione del flip-flop JK
0
1
×
×
K
×11
×01
110
000
JYy
Schema elettrico del flip-flop JK
y
y
J
K
C
Modulo 3 – U.D. 1 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 5
Flip-flop T
• Non ha segnali di dato.
• Ad ogni attivazione del segnale di controllo (o di Clock) T commuta le proprie uscite.
• Si realizza con un flip-flop JK con entrambi gli ingressi J e K sempre forzati a 1.
Tabella di eccitazione del flip-flop T
011
101
110
000
TYy
Modulo 3 – U.D. 1 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 6
Schema elettrico del flip-flop T
y
y
T
In sintesi...
Abbiamo a disposizione ulteriori elementi in grado di tenere memoria della sequenza di ingressi.
Sono non trasparenti: la funzione Master-Slave evita che le variazioni degli ingressi agiscano immediatamente sulle uscite.
Introducono disaccoppiamento fra ingressi e uscite.
Modulo 3 – U.D. 1 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 7
Chiusura
Modulo 3 – U.D. 2 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 1
Lezione 1 – Analisi di una rete sequenziale (parte 1)
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 2 - Analisi di una rete sequenziale
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Analisi di una rete sequenziale
S
R
y
y
2
2
S
R
y
y
1
1
x1x2
x1x2
x1x2
x1x2
x1
z2
z1
x2
Evidenziamo i legami combinatori fra ingressi alla rete, uscite dei bistabili e uscite della rete (vedi dispensa).
Modulo 3 – U.D. 2 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 2
Tabella di z in funzione di x e y
1
0
0
0
1
0
0
0
1
1
1
0
1
1
1
0
z1
15
14
11
9
6
4
1
0
#s
0111115
1011114
0101113
0001112
1110111
1010110
010019
100018
011107
101106
010105
000104
111003
101002
010001
100000
z2y2y1x2x1#
Stati STABILI e INSTABILI
Come evidenziato nella dispensa:• alcune configurazioni delle x e delle y sono
instabili: gli ingressi x provocano cambiamenti di stato dei bistabili che si traducono in variazioni delle y;
• dalla situazione precedente alla variazione di ingressi, ci si porta dunque a una diversa situazione a causa delle transizioni dei bistabili;
• si può distinguere fra stato presente dei bistabili(precedente alla transizione) e stato prossimo(successivo alla transizione).
Modulo 3 – U.D. 2 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 3
Stato PRESENTE e stato PROSSIMO
0111111115
1001011114
0011101113
0001001112
1111110111
1011010110
001010019
101000018
010111107
110101106
010010105
000000104
111011003
110001002
011010001
100000000
z2z1Y2Y1y2y1x2x1#
In sintesi...
Abbiamo esplicitato il funzionamento sequenziale con il concetto di stato presente e di stato prossimo.
Ci servono metodi di descrizione dei rapporti fra gli ingressi x alla rete, le variabili di stato presente y e di stato prossimo Y, le uscite della rete z.
Ove possibile, faremo ricorso a legami ormai familiari (i legami combinatori).
Andate a studiare la dispensa...
Modulo 3 – U.D. 2 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 4
Chiusura
Modulo 3 – U.D. 2 – Lez. 2
Nello Scarabottolo - Architetture e reti logiche 1
Lezione 2 – Analisi di una rete sequenziale (parte 2)
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 2 - Analisi di una rete sequenziale
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Ricapitolando...
In una rete sequenziale, variazioni agli ingressi (variabili x) possono provocare variazioni dello stato dei bistabili (variabili y):
• quando una configurazione degli ingressi non ècompatibile con lo stato presente dei bistabili, lo stato diviene instabile e provoca il passaggio a uno stato prossimo stabile differente;
• la descrizione tabellare (simile alla tabella delle verità combinatoria) vista nella lezione precedente evidenzia tale comportamento ma non consente di comprenderne le modalità di attuazione (gli ingressi ai bistabili non compaiono).
Introduciamo altre tabelle.
Modulo 3 – U.D. 2 – Lez. 2
Nello Scarabottolo - Architetture e reti logiche 2
Tabella delle uscite
Come indicato nella dispensa, fornisce le uscite z come funzione dello stato presente y e degli ingressi x:
Il legame è combinatorio: già noto!
0101111110
1110101111
0000101001
0100000100
10110100y1y2
x1x2z1z2
Tabella delle transizioni
Come indicato nella dispensa, fornisce lo stato prossimo Y come funzione dello stato presente y e degli ingressi x:
1110100010
1111100111
0111000101
0110000000
10110100y1y2
x1x2Y1Y2
Modulo 3 – U.D. 2 – Lez. 2
Nello Scarabottolo - Architetture e reti logiche 3
Dunque...
Dove stato presente e stato prossimo coincidono, lo stato è stabile, altrimenti èinstabile.
Il funzionamento è rappresentabile come un punto di lavoro situato in una casella della tabella:
• variazioni degli ingressi x provocano movimenti del punto di lavoro in orizzontale;
• se lo stato raggiunto è instabile, variano le yprovocando movimenti del punto di lavoro in verticale.
Tabella delle eccitazioni della rete
Come indicato nella dispensa, riporta il legame fra ingressi alla rete, stato presente e ingressi ai bistabili:
00,1010,0000,0101,0010
00,1010,0000,0101,0011
00,1010,0000,0101,0001
00,1010,0000,0101,0000
10110100y1y2
x1x2S1R1,S2R2
Modulo 3 – U.D. 2 – Lez. 2
Nello Scarabottolo - Architetture e reti logiche 4
Transizioni e eccitazioni
Come illustrato nella dispensa, sono legate dalla tabella delle eccitazioni del bistabileusato:
Le eccitazioni della rete sono gli ingressi ai bistabili necessari per far evolvere lo stato presente y verso l'opportuno stato prossimo Y.
0×11
1001
0110
×000
RSYy
In sintesi...
Abbiamo effettuato una analisi del funzionamento sequenziale con una serie di tabelle che mettono in relazione:
• gli ingressi x alla rete;• le variabili di stato presente y e di stato prossimo Y;• le uscite della rete z e gli ingressi dei bistabili.
Dobbiamo ora passare alla sintesi: dal funzionamento atteso, a una possibile struttura circuitale che lo realizzi.
Prima però introduciamo - nella prossima lezione -una notazione simbolica degli stati.
Modulo 3 – U.D. 2 – Lez. 2
Nello Scarabottolo - Architetture e reti logiche 5
Chiusura
Modulo 3 – U.D. 2 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 1
Lezione 3 – Rappresentazione simbolica degli stati
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 2 - Analisi di una rete sequenziale
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Come visto nella lezione precedente...
La tabella delle transizioni fornisce lo stato prossimo Y come funzione dello stato presente y e degli ingressi x.
Il funzionamento della rete è rappresentabile come un punto di lavoro situato in una casella della tabella:
• variazioni degli ingressi x provocano movimenti del punto di lavoro in orizzontale;
• se lo stato raggiunto è instabile, variano le yprovocando movimenti del punto di lavoro in verticale.
Modulo 3 – U.D. 2 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 2
Tabella degli stati
Della tabella delle transizioni, si può dare una rappresentazione simbolica, che trascuri le codifiche binarie degli stati:
La tabella riporta lo stato prossimo S in fun-zione dello stato presente s e degli ingressi x.
cddad
ccdbc
bcabb
bdaaa
10110100s
x1x2S
Diagramma degli stati
Modulo 3 – U.D. 2 – Lez. 3
Nello Scarabottolo - Architetture e reti logiche 3
In sintesi...
Tabella degli stati: definizione simbolica del comportamento della rete sequenziale.Diagramma degli stati: una versione grafica della tabella, per evidenziare ulteriormente quali eventi esterni (le variazioni degli ingressi x) provocano quali transizioni interne (le variazioni di stato s).Uscite: possono comparire associate agli archi del diagramma (transizioni) o ai nodi del diagramma (stati):
• vedremo nelle prossime lezioni quando e perchéscegliere una o l'altra situazione.
Chiusura
Modulo 3 – U.D. 3 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 1
Lezione 1 – Reti sequenziali sincrone
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 3 - Sintesi di una rete sequenziale sincrona
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Reti sequenziali sincrone
È presente un segnale periodico di sincronismo (clock) avente la seguente forma:
Si possono usare bistabili master-slave(flip-flop) attivati dal segnale di clock.
• Durante l'inattività del master (clock=0) gli ingressi alla rete possono variare liberamente (flip-flop "spenti").
• Durante l'attività del master, gli ingressi devono rimanere stabili per consentire ai flip-flop di variare correttamente il proprio stato.
Modulo 3 – U.D. 3 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 2
Macchine alla Mealy
Macchine alla Mealy
Uscite funzione di ingressi e stato presente.• Reagiscono immediatamente a variazioni degli
ingressi:– sono rapide;
– sono trasparenti;
– gli ingressi devono variare più lentamente del clock per evitare oscillazioni spurie delle uscite.
Associamo i valori di uscita agli archi del diagramma degli stati (transizioni).
Modulo 3 – U.D. 3 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 3
Diagramma degli stati alla Mealy
Macchine alla Moore
Modulo 3 – U.D. 3 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 4
Macchine alla Moore
Uscite funzione solo dello stato presente.• Reagiscono a variazioni degli ingressi solo al
prossimo "colpo" di clock:– sono meno rapide delle macchine di Mealy;
– NON sono trasparenti;
– variazioni anche rapide degli ingressi durante la fase di inattività del master vengono filtrate automaticamente.
Associamo i valori di uscita ai nodi (stati) deldiagramma degli stati.
Diagramma degli stati alla Moore
Modulo 3 – U.D. 3 – Lez. 1
Nello Scarabottolo - Architetture e reti logiche 5
In sintesi...
Nelle macchine sequenziali sincrone esiste un clock che dà il ritmo di lavoro:
• si possono usare bistabili master-slave;• in presenza di i ingressi alla rete, in ogni stato si
possono presentare 2i configurazioni di ingresso;• in una macchina alla Mealy (più veloce ma meno
robusta) i valori di uscita vengono associati alle transizioni di stato;
• in una macchina alla Moore (meno veloce ma piùrobusta) i valori di uscita vengono associati agli stati.
Chiusura
Modulo 3 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Sintesi di una macchina sincrona alla Mealy
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 3 - Sintesi di una rete sequenziale sincrona
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Diagramma degli stati alla Mealy
Rete con un ingresso x e un'uscita z, che riconosce la sequenza di ingresso 101.La sequenza può presentarsi dopo vari bit:1110011100011101.Le sequenze riconosciute NON possono concatenarsi: 1010101.
Modulo 3 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Tabella degli stati
d
c
b
a
10s
xS,z
Tabelle delle transizioni e delle uscite
b , 0a , 0d
d , 1a , 0c
b , 0c , 0b
b , 0a , 0a
10s
xS,z
10
11
01
00
10y1y2
xY1Y2
Scegliamo arbitrariamente 4 codifiche binarie per i 4 stati della tabella degli stati:
10
11
01
00
10y1y2
xz
Modulo 3 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Prossimo passo
La tabella delle uscite consente la sintesi combinatoria della funzione:
z = f (x, y1, y2)
La tabella delle transizioni ci dice come devono variare gli stati dei bistabili in corrispondenza delle diverse configurazioni di ingresso:
• dobbiamo scegliere il tipo di bistabile da utilizzare, e ricorrere alla tabella di eccitazione del bistabileper costruire la tabella di eccitazione della rete;
• scegliamo il flip-flop SR.
Tabella delle eccitazioni
010010
100011
011101
010000
10y1y2
xY1Y2
10
11
01
00
10y1y2
xS1R1,S2R2
0×11
1001
0110
×000
RSYy
Modulo 3 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Sintesi della rete
La tabella delle eccitazioni consente la sintesi combinatoria delle 4 funzioni:
S1 = f (x, y1, y2)R1 = f (x, y1, y2)S2 = f (x, y1, y2)R2 = f (x, y1, y2)
Abbiamo completato la sintesi della rete sequenziale sincrona alla Mealy.
In sintesi...
Dal diagramma degli stati, arriviamo alla sintesi della macchina alla Mealy mediante:
• costruzione della tabella degli stati;• scelta della codifica degli stati;• costruzione della tabella delle transizioni e
della tabella delle uscite;• scelta del tipo di bistabile;• costruzione della tabella delle eccitazioni della
rete;• sintesi combinatoria delle eccitazioni e delle
uscite.
Modulo 3 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Chiusura
Modulo 3 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Sintesi di una macchina sincrona alla Moore
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 3 - Sintesi di una rete sequenziale sincrona
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Diagramma degli stati alla Moore
Rete con un ingresso x e un'uscita z, che riconosce la sequenza di ingresso 101.
Modulo 3 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Tabella degli stati
z
d
c
b
a
10s
xS
Tabelle delle transizioni e delle uscite
1
0
0
0
z
bad
dac
bcb
baa
10s
xS
10
11
01
00
10y1y2
xY1Y2
Scegliamo arbitrariamente 4 codifiche binarie per i 4 stati della tabella degli stati:
10
11
01
00
zy1y2
Modulo 3 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Prossimo passo
La tabella delle uscite consente la sintesi combinatoria della funzione:
z = f (y1, y2)
La tabella delle transizioni ci dice come devono variare gli stati dei bistabili in corrispondenza delle diverse configurazioni di ingresso:
• dobbiamo scegliere il tipo di bistabile da utilizzare, e ricorrere alla tabella di eccitazione del bistabileper costruire la tabella di eccitazione della rete.
• scegliamo il flip-flop JK.
Tabella delle eccitazioni
010010
100011
011101
010000
10y1y2
xY1Y2
10
11
01
00
10y1y2
xJ1K1,J2K2
0×11
1×01
×110
×000
KJYy
Modulo 3 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Sintesi della rete
La tabella delle eccitazioni consente la sintesi combinatoria delle 4 funzioni:
J1 = f (x, y1, y2)K1 = f (x, y1, y2)J2 = f (x, y1, y2)K2 = f (x, y1, y2)
Abbiamo completato la sintesi della rete sequenziale sincrona alla Moore.
In sintesi...
Dal diagramma degli stati, arriviamo alla sintesi della macchina alla Moore mediante:
• costruzione della tabella degli stati;• scelta della codifica degli stati;• costruzione della tabella delle transizioni e
della tabella delle uscite;• scelta del tipo di bistabile;• costruzione della tabella delle eccitazioni della
rete;• sintesi combinatoria delle eccitazioni e delle
uscite.
Modulo 3 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
Chiusura
Modulo 3 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 4 – Dalle specifiche al diagramma degli stati
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 3 - Sintesi di una rete sequenziale sincrona
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Costruire il diagramma degli stati
È la parte più difficile perché non ci sono regole universali, solo suggerimenti:
• individuare uno stato iniziale, dal quale parte la sequenza di eventi che la rete deve riconoscere;
• definire prima la sequenza utile (o le sequenze utili);
• esaurire poi il diagramma con le sequenze inutili;• verificare se esistono stati già incontrati;• ricordare il problema della concatenazione delle
sequenze utili (possono sovrapporsi o no?);• individuare e verificare eventuali simmetrie (per
es.: l'uscita commuta se...).
Modulo 3 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 2
Primo esempio
Progettare un rivelatore binario delle sequenze 010 e 0010.
Il dispositivo elettronico è fornito di un ingresso x e un'uscita z che viene portata a 1 quando viene riconosciuta una delle due sequenze, e torna a 0 all’arrivo del bit successivo.
Si noti che il dispositivo deve continuare a cercare le sequenze, ma che tali sequenze NON possono concatenarsi (cioè lo 0 finale di una sequenza non può coincidere con lo 0 iniziale della successiva).
Diagramma degli stati (Mealy)
Modulo 3 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 3
Secondo esempio
Progettare una macchina sequenziale sincrona, dotata di due ingressi x1 e x2 e di un’uscita z.
Ogni tre periodi di clock, l’uscita z passa a 1 se e solo se si sono presentati almeno una volta due zeri simultanei agli ingressi.
L'uscita z torna a 0 al successivo colpo di clock.
Diagramma degli stati (Moore)
Modulo 3 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 4
Terzo esempio
Progettare una macchina sequenziale sincrona, dotata di un ingresso x e di due uscite z1 e z2 .
L’uscita z1 commuta quando riconosce la sequenza 101.
L'uscita z2 passa a 1 quando riconosce la sequenza 1100 e torna a 0 al successivo colpo di clock.
Le sequenze NON possono concatenarsi.
Diagramma degli stati (Moore)
a/00 b/00 d/10c/00 e/10
g/00
h/00
i/01
a1
j/10
k/10
l/11
0 1
0
1
0
0
1
0
0
1 1
a
0
f/101 0 1
0
1
0b
1a
a
0e
1d
1d
d
0
Modulo 3 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 5
In sintesi...
Il tracciamento del diagramma degli stati a partire dalle specifiche è l'attività che richiede maggiore esercizio e capacità progettuale.
Serve allenarsi per raggiungere una sufficiente familiarità con l'attività.
È opportuno non inserire un numero eccessivo di stati, ma in caso di dubbio meglio abbondare: nella prossima lezione vedremo come eliminare eventuali stati "inutili".
Chiusura
Modulo 3 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Indistinguibilità fra gli stati di una rete sequenziale
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 4 - Ottimizzazione della sintesi di una rete sequenziale sincrona
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Ottimizzazione delle reti sequenziali
Come sempre, cerchiamo di ottenere lo stesso risultato (comportamentale) con il minimo impegno (strutturale).
Oltre alle ottimizzazioni combinatorie, cerchiamo possibili punti di intervento per ottimizzare le scelte sequenziali.
Un tipico punto di intervento è il numero di stati del diagramma. Se riduciamo gli stati:
• possiamo ridurre il numero di bistabili necessari;• abbiamo più gradi di libertà (indifferenze) nella
sintesi delle parti combinatorie.
Modulo 3 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Indistinguibilità
Due stati si e sj sono indistinguibili se:• per ogni possibile sequenza di ingresso applicata
a partire da si e sj;• le sequenze di uscita coincidono.
Si verifica l'indistinguibilità se:1. le uscite associate a si e sj per ogni possibile
configurazione di ingresso sono uguali;2. gli stati prossimi associati a si e sj per ogni
possibile configurazione di ingresso sono indistinguibili.
Come procedere
Si confrontano tutte le coppie di stati della tabella degli stati. Si identificano:
• stati distinguibili;• stati indistinguibili;• stati che richiedono l'indistinguibilità di altri
stati.Per questi ultimi si può successivamente trovare:
• sicura distinguibilità;• sicura indistinguibilità;• condizioni circolari (da cui consegue
indistinguibilità).
Modulo 3 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
In sintesi...
Il concetto di indistinguibilità consente di ridurre il numero di stati eliminando eventuali ridondanze inserite in fase di progetto del diagramma degli stati.
Serve un metodo per il confronto di tutte le possibili coppie di stati, e per l'individuazione di quelli indistinguibili.
Chiusura
Modulo 3 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Tabella e grafo delle indistinguibilità
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 4 - Ottimizzazione della sintesi di una rete sequenziale sincrona
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Esempio di diagramma degli stati
Modulo 3 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Tabella degli stati corrispondente
a , 0b , 0g
a , 0g , 1f
a , 0b , 0e
f , 0d , 0d
a , 0e , 1c
c , 0d , 0b
a , 0b , 0a
10s
xS,z
Tabella delle indistinguibilità
Costruiamo un "girone all'italiana" fra i vari stati.
Per ogni coppia di stati, indichiamo:• distinguibilità (simbolo ×);• indistinguibilità (simbolo ~);• condizione di indistinguibilità (coppie di stati che
devono essere indistinguibili per garantire l'indistinguibilità).
Dopo il primo giro, risolviamo i punti interrogativi rimasti.
Modulo 3 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Tabella delle indistinguibilità
a , 0b , 0g
a , 0g , 1f
a , 0b , 0e
f , 0d , 0d
a , 0e , 1c
c , 0d , 0b
a , 0b , 0a
10s
xS,z
fedcba
g
f
e
d
c
b
Grafo delle indistinguibilità
Nodi: gli stati.Archi: le indistinguibilità (eventualmente condizionate).Scopo: individuare gruppi di stati tra loro indistinguibili.
Modulo 3 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Tabella degli stati ridotta
Dalla tabella degli stati......al grafo delle indistinguibilità, che riunisce gruppi di stati fra loro indistinguibili.
Ripartiamo dalla tabella degli stati:• per ogni stato (riga) facciamo riferimento al
gruppo di stati nella tabella ridotta che contiene tale stato;
• riempiamo in questo modo la tabella ridotta.
Poi proseguiamo nella sintesi normale.
Tabella ridotta
a , 0b , 0g
a , 0g , 1f
a , 0b , 0e
f , 0d , 0d
a , 0e , 1c
c , 0d , 0b
a , 0b , 0a
10s
xS,z
γ
β
α
10s
xS,z
Modulo 3 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
In sintesi...
Individuiamo gli eventuali gruppi di stati fra loro indistinguibili, che possono essere riuniti in un unico stato.
Riportiamo tali gruppi di stati in una tabella degli stati ridotta.
Poi proseguiamo con la sintesi normale.
Chiusura
Modulo 3 – U.D. 5 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Differenze tra reti asincrone impulsive e reti sincrone
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 5 - Sintesi di una rete sequenziale asincrona impulsiva
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Comportamento degli ingressi
Ogni ingresso è indipendente.Tra due impulsi su due ingressi diversi la rete deve avere il tempo di assestarsi.
La somma logica (OR) degli ingressi può essere usata al posto del segnale di clock delle reti sincrone (quindi stessi bistabili master-slave).
Modulo 3 – U.D. 5 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Diagramma degli stati alla Mealy
In presenza di i ingressi alla rete, in ogni stato si possono presentare i impulsi di ingresso diversi (uno su ogni ingresso).
I valori di uscita sono associati alle transizioni di stato (archi del grafo).
Macchine alla Mealy
• Valori di uscita associati alle transizioni;
• transizioni corrispondenti a impulsi sugli ingressi.
Comportamento impulsivo delle uscite: un 1 in uscita corrisponde a un impulso dell'uscita a seguito della transizione di stato corrispondente.
Modulo 3 – U.D. 5 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Diagramma degli stati alla Moore
In presenza di i ingressi alla rete, in ogni stato si possono presentare i impulsi di ingresso diversi (uno su ogni ingresso).
I valori di uscita sono associati agli stati (nodidel grafo).
Macchine alla Moore
• Valori di uscita associati agli stati;
• stati corrispondenti a situazioni stazionarie della rete a seguito di impulsi sugli ingressi.
Comportamento stazionario delle uscite: uno 0 o un 1 in uscita permangono finché la rete si trova nello stato corrispondente.
Modulo 3 – U.D. 5 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
Nell'ipotesi di impulsi separati nel tempo sui vari ingressi, possiamo ricondurre la rete asincrona impulsiva a una rete sincrona, nella quale il clock è l'OR degli ingressi.
In ogni stato, si possono presentare un numero di eventi diversi (impulsi) pari al numero di ingressi (e non al numero di possibili configurazioni binarie degli ingressi, come nelle reti sincrone).
Le macchine alla Mealy hanno uscite impulsive.
Le macchine alla Moore hanno uscite stazionarie.
Chiusura
Modulo 3 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Sintesi di una macchina asincrona impulsiva alla Mealy
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 5 - Sintesi di una rete sequenziale asincrona impulsiva
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Diagramma degli stati alla Mealy
Rete con due ingressi A e B e un'uscita z, che riconosce la sequenza di ingresso ABB.
Modulo 3 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Tabella degli stati
d
c
b
a
BAs
INS,z
Tabella e grafo delle indistinguibilità
a , 0b , 0d
d , 1b , 0c
c , 0b , 0b
a , 0b , 0a
BAs
INS,z
cba
d
c
b
c
b
α
BAs
INS,z
Tabella degli stati ridotta:
Modulo 3 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Tabelle delle transizioni e delle uscite
α , 1b , 0c
c , 0b , 0b
α , 0b , 0α
BAs
INS,z
11
01
00
BAy1y2
INY1Y2
Scegliamo arbitrariamente 3 codifiche binarie per i 3 stati della tabella degli stati:
11
01
00
BAy1y2
INz
Sintesi dell'uscita
Le due colonne A e B della tabella delle uscite sono indipendenti (l'impulso di ingresso può verificarsi su A oppure su B).
La tabella delle uscite consente la sintesi combinatoria delle due funzioni indipendenti:
zA = f (y1, y2) a seguito di impulso su A;zB = f (y1, y2) a seguito di impulso su B.
L'uscita z vera e propria è dunque l'OR di zA e zBa seconda di quale dei due ingressi ha generato l'impulso:
in questo modo è funzione anche degli ingressi, come normale in una macchina alla Mealy.
Modulo 3 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Rete di generazione dell'uscita z
Tabella delle eccitazioni
000111
110101
000100
BAy1y2
INY1Y2
11
01
00
BAy1y2
INS1R1,S2R2
0×11
1001
0110
×000
RSYy
Modulo 3 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Sintesi della rete
Le due colonne A e B della tabella delle eccitazioni sono indipendenti (l'impulso di ingresso può verificarsi su A oppure su B).
La tabella delle eccitazioni consente la sintesi combinatoria delle 8 funzioni:
S1,A = f (y1, y2) S1,B = f (y1, y2)R1,A = f (y1, y2) R1,B = f (y1, y2)S2,A = f (y1, y2) S2,B = f (y1, y2)R2,A = f (y1, y2) R2,B = f (y1, y2)
Ogni eccitazione è dunque l'OR di due reti combinatorie, a seconda di quale dei due ingressi ha generato l'impulso.
Rete di generazione delle eccitazioni
Modulo 3 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 6
In sintesi...
La sintesi della rete asincrona segue lo stesso iter di quello delle reti sequenziali sincrone alla Mealy ma:
• da ogni stato si esce con un numero di archi pari al numero di ingressi;
• le varie colonne della tabella delle uscite e della tabella delle eccitazioni sono indipendenti;
• ogni colonna consente la costruzione di una rete combinatoria indipendente;
• la rete finale richiede l'OR delle uscite delle varie reti combinatorie, ciascuna condizionata mediante porta AND alla presenza dell'impulso di ingresso corripondente.
Chiusura
Modulo 3 – U.D. 5 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Sintesi di una macchina asincrona impulsiva alla Moore
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 5 - Sintesi di una rete sequenziale asincrona impulsiva
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Diagramma degli stati alla Moore
Rete con due ingressi A e B e un'uscita z, che riconosce la sequenza di ingresso BBA.
Modulo 3 – U.D. 5 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Tabella degli stati
z
d
c
b
a
BAs
INS
Tabella e grafo delle indistinguibilità
1
0
0
0
z
bad
cdc
cab
baa
BAs
INS
cba
d
c
b
La tabella degli stati è già minima.
Modulo 3 – U.D. 5 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Tabelle delle transizioni e delle uscite
1
0
0
0
z
bad
cdc
cab
baa
BAs
INS
10
11
01
00
BAy1y2
INY1Y2
Scegliamo arbitrariamente 4 codifiche binarie per i 4 stati della tabella degli stati:
10
11
01
00
y1y2
z
Sintesi dell'uscita
La tabella delle uscite consente la sintesi combinatoria della funzione:
z = f (y1, y2)
La funzione dipende SOLO dallo stato presente, come normale in una macchina alla Moore.
Modulo 3 – U.D. 5 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Tabella delle eccitazioni
010010
111011
110001
010000
BAy1y2
INY1Y2
10
11
01
00
BAy1y2
INJ1K1,J2K2
0×11
1×01
×110
×000
KJYy
Sintesi della rete
Le due colonne A e B della tabella delle eccitazioni sono indipendenti (l'impulso di ingresso può verificarsi su A oppure su B).
La tabella delle eccitazioni consente la sintesi combinatoria delle 8 funzioni:
J1,A = f (y1, y2) J1,B = f (y1, y2)K1,A = f (y1, y2) K1,B = f (y1, y2)J2,A = f (y1, y2) J2,B = f (y1, y2)K2,A = f (y1, y2) K2,B = f (y1, y2)
Ogni eccitazione è dunque l'OR di due reti combinatorie, in base a quale dei due ingressi ha generato l'impulso.
Modulo 3 – U.D. 5 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
Rete di generazione delle eccitazioni
In sintesi...
La sintesi segue lo stesso iter di quello delle reti sequenziali sincrone alla Moore ma:
• da ogni stato si esce con un numero di archi pari al numero di ingressi;
• l'uscita è una normale rete combinatoria funzione del solo stato presente;
• le varie colonne della tabella delle eccitazioni sono indipendenti;
• ogni colonna consente la costruzione di una rete combinatoria indipendente;
• la rete finale richiede l'OR delle uscite delle varie reti combinatorie, ciascuna condizionata mediante porta AND alla presenza dell'impulso di ingresso corripondente.
Modulo 3 – U.D. 5 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 6
Chiusura
Modulo 3 – U.D. 5 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 1
Esercitazione didattica
Come costruire una macchina asincrona impulsiva a partire dalle specifiche (primo esempio)
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 5 - Sintesi di una rete sequenziale asincrona impulsiva
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Primo esempio
Progettare una rete sequenziale asincrona impulsiva dotata di tre ingressi A, B e C e di un’uscita z. L’uscita z commuta ogniqualvolta si presentano due impulsi consecutivi sul medesimo ingresso.
• Perché l'uscita possa commutare (cioè passare da 0 a 1 o viceversa) deve essere un'uscita a livelli, quindi: macchina alla Moore.
• Poiché ciò che serve per far passare z da 0 a 1 serve anche per far ritornare z da 1 a 0, il diagramma deve essere simmetrico.
Modulo 3 – U.D. 5 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 2
Diagramma e tabella degli stati
f
e
C z
d
c
b
a
BAs
INS
Tabella e grafo delle indistinguibilità
c
f
f
f
c
c
C
1edf
1bde
1
0
0
0
z
ead
bac
eab
bda
BAs
INS
b
c
edcba
f
e
d
La tabella degli stati è già minima.
Modulo 3 – U.D. 5 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 3
Tabelle delle transizioni e delle uscite
C
101
100
011
010
001
000
BAy1y2y3
INY1Y2Y3
Scegliamo arbitrariamente 6 codifiche binarie per i 6 stati della tabella degli stati:
101
100
011
010
001
000
y1y2y3
z
c
f
f
f
c
c
C
1edf
1bde
1
0
0
0
z
ead
bac
eab
bda
BAs
INS
Tabella delle eccitazioni
C
101
100
011
010
001
000
BAy1y2
INS1R1,S2R2,S3R3
0×11
1001
0110
×000
RSYy
010
101
101
101
010
010
C
100011101
001011100
100000011
001000010
100000001
001011000
BAy1y2y3
INY1Y2Y3
Modulo 3 – U.D. 5 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 4
Chiusura
Modulo 3 – U.D. 5 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 1
Esercitazione didattica
Come costruire una macchina asincrona impulsiva a partire dalle specifiche (secondo esempio)
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 5 - Sintesi di una rete sequenziale asincrona impulsiva
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Secondo esempio
Progettare una macchina sequenziale asincrona funzionante in modo impulsivo, dotata di tre ingressi A, B e C e di un’uscita z. L’uscita zgenera un impulso in corrispondenza di un impulso sull’ingresso A, ma solo se nell’intervallo di tempo intercorso tra tale impulso e il precedente impulso su A si è verificata almeno una volta la sequenza di impulsi B C B C.
• Perché l'uscita possa generare un impulso, deve essere una macchina alla Mealy.
Modulo 3 – U.D. 5 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 2
Diagramma e tabella degli stati
f
e
C
d
c
b
a
BAs
INS,z
Tabella e grafo delle indistinguibilità
a , 0
e , 0
e , 0
a , 0
c , 0
a , 0
C
b , 0a , 0f
e , 0f , 1e
b , 0a , 0d
d , 0a , 0c
b , 0a , 0b
b , 0a , 0a
BAs
INS,zb
c
edcba
f
e
d
C
e
d
c
b
α
BAs
INS,z
Tabella degli stati ridotta:
Modulo 3 – U.D. 5 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 3
Tabelle delle transizioni e delle uscite
e , 0
e , 0
α , 0
c , 0
α , 0
C
e , 0α , 1e
b , 0α , 0d
d , 0α , 0c
b , 0α , 0b
b , 0α , 0α
BAs
INS,z
C
100
011
010
001
000
BAy1y2y3
INY1Y2Y3
Scegliamo arbitrariamente 5 codifiche binarie per i 5 stati della tabella degli stati:
C
100
011
010
001
000
BAy1y2y3
INz
Tabella delle eccitazioni
C
100
011
010
001
000
BAy1y2y3
INJ1K1,J2K2,J3K3
0×11
1×01
×110
×000
KJYy
100
100
000
010
000
C
100000100
001000011
011000010
001000001
001000000
BAy1y2y3
INY1Y2Y3
Modulo 3 – U.D. 5 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 4
Chiusura
Modulo 3 – U.D. 6 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Reti asincrone funzionanti in modo fondamentale
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 6 - Sintesi di una rete sequenziale asincrona in modo fondamentale
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Comportamento degli ingressi
• Ogni ingresso è indipendente.• Ogni variazione (fronte) degli ingressi è un
evento significativo.• Non è possibile estrarre un segnale di
sincronismo: dobbiamo usare bistabili trasparenti (latch).
Modulo 3 – U.D. 6 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Diagramma degli stati
In presenza di i ingressi alla rete, in ogni stato si possono presentare i+1 configurazioni di ingresso diverse:
• quella che ci fa rimanere nello stato (autoanello);• le altre i a distanza di Hamming unitaria.
Comportamento degli stati
Manca il segnale di sincronismo:• il punto di lavoro non si muove ad ogni colpo di
clock, ma è "sempre in movimento" in attesa del primo evento di ingresso;
• normalmente, gira sull'autoanello associato allo stato;
• se nella transizione fra due stati un'uscita deve variare, è indifferente cosa fa durante la transizione;
• e scompare la differenza Mealy-Moore!
Modulo 3 – U.D. 6 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
In sintesi...
La rete asincrona funzionante in modo fondamentale richiede una sintesi con bistabili trasparenti (latch).
Non esiste differenza Mealy-Moore.
Ogni stato è caratterizzato da un autoanello, nel quale il punto di lavoro ruota finché non si verificano fronti sugli ingressi.
Il numero di eventi che innescano transizioni fra gli stati (fronti sugli ingressi) è pari al numero di ingressi.
Chiusura
Modulo 3 – U.D. 6 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Sintesi di una macchina asincrona in modo fondamentale
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 6 - Sintesi di una rete sequenziale asincrona in modo fondamentale
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Diagramma degli stati
Rete con due ingressi A e B e un'uscita z, che riconosce la sequenza di ingresso ↓B ↓A.
Modulo 3 – U.D. 6 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Tabella degli stati
f
e
1011
d
c
b
a
0100s
ABS,z
Tabella delle compatibilità
Come per le indistinguibilità, costruiamo un "girone all'italiana" fra i vari stati.
Per ogni coppia di stati, indichiamo:• incompatibilità (simbolo ×);• compatibilità (simbolo ∨);• condizione di compatibilità (coppie di stati che
devono essere compatibili per garantire la compatibilità).
Dopo il primo giro, risolviamo i punti interrogativi rimasti.
Modulo 3 – U.D. 6 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Tabella delle compatibilità
f , 0a , 0-e , 0f
f , 0-d , 0e , 0e
-
f , ×
b , 0
b , 0
10
a , 0
-
a , 0
a , 0
11
d , 0e , 0d
d , ×c , 1c
-c , ×b
d , 0-a
0100s
ABS,z
b
c
edcba
f
e
d
Grafo delle compatibilità
I gruppi di stati compatibili (a differenza di quelli indistinguibili) non sono disgiunti!
∨b
b,fb,fc
e
∨
d
∨
∨
cba
c,fb,ff
c,e b,fb,fe
c,e∨d
Scegliamo i gruppi più convenienti (grossi).
Modulo 3 – U.D. 6 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Tabella ridotta
f , 0a , 0-e , 0f
f , 0-d , 0e , 0e
-
f , ×
b , 0
b , 0
10
a , 0
-
a , 0
a , 0
11
d , 0e , 0d
d , ×c , 1c
-c , ×b
d , 0-a
0100s
ABS,z
1011
β
c
α
0100s
ABS,z
Ora si procede come per una normale sintesi.
Tabelle delle transizioni e delle uscite
β , 0
β , ×
α , 0
10
α , 0
-
α , 0
11
β , 0β , 0β
β , ×c , 1c
β , 0c , ×α
0100s
ABS,z
1011
11
01
00
0100y1y2
ABY1Y2
Scegliamo arbitrariamente 3 codifiche binarie per i 3 stati della tabella degli stati:
1011
11
01
00
0100y1y2
ABz
Modulo 3 – U.D. 6 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Prossimo passo
La tabella delle uscite consente la sintesi combinatoria della funzione:
z = f (A, B, y1, y2)
La tabella delle transizioni ci dice come devono variare gli stati dei bistabili in corrispondenza delle diverse configurazioni di ingresso:
• dobbiamo fare uso del bistabile trasparente (latch) di tipo SR;
• dobbiamo ricorrere alla tabella di eccitazione del bistabile per costruire la tabella di eccitazione della rete.
Tabella delle eccitazioni
11
11
00
10
00
××
00
11
111111
110101
110100
0100y1y2
ABY1Y2
1011
11
01
00
0100y1y2
ABS1R1,S2R2
0×11
1001
0110
×000
RSYy
Modulo 3 – U.D. 6 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 6
Sintesi della rete
La tabella delle eccitazioni consente la sintesi combinatoria delle 4 funzioni:
S1 = f (A, B, y1, y2)R1 = f (A, B, y1, y2)S2 = f (A, B, y1, y2)R2 = f (A, B, y1, y2)
Abbiamo completato la sintesi della rete sequenziale asincrona funzionante in modo fondamentale.
In sintesi...
La sintesi delle reti sequenziali asincrone funzionanti in modo fondamentale segue lo stesso iter di quello delle reti sequenziali sincrone ma:
• da ogni stato si esce con un numero di archi pari al numero di ingressi (oltre all'autoanellodi permanenza nello stato);
• la minimizzazione sfrutta il concetto di compatibilità (che porta a gruppi di stati compatibili non disgiunti);
• i bistabili da utilizzare sono bistabili trasparenti (latch) di tipo SR.
Modulo 3 – U.D. 6 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 7
Chiusura
Modulo 3 – U.D. 6 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Corse e corse critiche
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 6 - Sintesi di una rete sequenziale asincrona in modo fondamentale
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Tabelle degli stati e delle transizioni
Da 0001 a 0000 variando B:• si raggiunge c passando per b o d (corsa).
Da 0011 a 0010 variando B:• si può raggiungere c passando per d oppure
restare "intrappolati" in b (corsa critica).
cdbcd
c
b
c
10
d
b
a
11
acc
bcb
aca
0100s
ABS
1110011110
11
01
11
10
10
01
00
11
001111
011101
001100
0100y1y2
ABY1Y2
Modulo 3 – U.D. 6 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Corse e corse critiche
La corsa (malfunzionamento transitorio) è un passaggio fra due stati associati a due codifiche delle variabili di stato a distanza di Hammingmaggiore di 1.
I diversi ritardi di commutazione dei bistabiliportano ad attraversare uno o più stati intermedi spuri.
Se uno degli stati intermedi spuri è stabile, la macchina viene intrappolata in uno stato diverso da quello desiderato: si è in presenza di una corsa critica (malfunzionamento permanente).
Eliminazione delle corse
Le corse (quindi anche le corse critiche) si eliminano imponendo distanza di Hammingunitaria fra le codifiche delle variabili di stato di tutte le coppie di stati adiacenti (cioè tutte le possibili coppie stato presente - stato prossimo).
Se necessario, si ricorre a codifiche ridondanti (codifiche multiple per uno stesso stato) che:
• garantiscano le necessarie adiacenze con gli altri stati;
• siano fra loro adiacenti.
Modulo 3 – U.D. 6 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Grafo delle adiacenze
Nodi: gli stati della macchina.Archi: le connessioni fra le possibili coppie di stato presente e stato prossimo.
cdbcd
c
b
c
10
d
b
a
11
acc
bcb
aca
0100s
ABS
Codifiche ridondanti
Nel nostro esempio, servono 3 variabili di stato (con 2, infatti, non riusciamo a garantire le necessarie adiacenze).
1
0
10110100y1
y2y3
Modulo 3 – U.D. 6 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Tabella degli stati ridondanti
cdbcd
c
b
c
10
d
b
a
11
acc
bcb
aca
0100s
ABS
d2b1
d1ca0
10110100y1
y2y3
d2
d1
1011
c
b
a
0100s
ABS
In sintesi...
La corsa è un malfunzionamento legato alle differenti codifiche fra stati adiacenti.
In caso di corsa critica, il malfunzionamento assume carattere permanente.
L'eliminazione delle corse presuppone stati adiacenti a distanza di Hamming unitaria.
Per ottenere tale risultato, servono codifiche ridondanti.
Si utilizza una mappa di Karnaugh sulla quale, per tentativi, si posizionano gli stati in modo da ottenere il risultato desiderato.
Modulo 3 – U.D. 6 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
Chiusura
Modulo 3 – U.D. 6 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 1
Esercitazione didattica
Come costruire una macchina asincrona fondamentale a partire dalle specifiche
Architetture e reti logiche
Modulo 3 - Progettazione di una rete sequenziale
Unità didattica 6 - Sintesi di una rete sequenziale asincrona in modo fondamentale
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Esempio
Progettare una macchina sequenziale asincrona funzionante in modo fondamentale, dotata di due ingressi A e B e di una uscita z.L’uscita z passa a 1 se si verifica un impulso positivo sull’ingresso A (cioè un fronte di salita seguito da un fronte di discesa) mentre l’ingresso B vale 1, e torna a 0 se si verifica un impulso positivo su A mentre B vale 0.
• La sequenza utile perché l'uscita passi da 0 a 1 è:01 → 11 → 01
• La sequenza utile perché l'uscita torni da 1 a 0 è:00 → 10 → 00
Modulo 3 – U.D. 6 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 2
Diagramma degli stati
Tabella degli stati
l
i
h
g
f
e
1011
d
c
b
a
0100s
ABS,z
Modulo 3 – U.D. 6 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 3
Tabella degli stati
l , 1i , 1-d , 1l
l , 1i , 1c , 1-i
g , 0h , 0a , 0-h
g , 0h , 0-f , 0g
g , 0-a , 0f , 0f
e , 1i , 1-f , ×e
e , 1
-
g , 0
-
10
-
i , 1
b , 0
b , 0
11
c , 1d , 1d
c , 1d , 1c
c , ×-b
a , 0f , 0a
0100s
ABS,z
Tabella e grafo delle compatibilità
i
∨
hg
∨
f
∨
∨
a,cb
c
∨d
d,fd,fe
a,c∨f
b,hb,hg
e
d,f
e,l
d
e,l
e,l
c
∨
∨
ba
l
i
a,cb,hh
Modulo 3 – U.D. 6 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 4
Tabella degli stati ridotta
β
e
1011
d
α
b
a
0100s
ABS,z
Tabella degli stati ridotta
β , 0β , 0a , 0β , 0β
e , 1α , 1-β , ×e
e , 1
α , 1
β , 0
-
10
-
α , 1
b , 0
b , 0
11
α , 1d , 1d
α , 1d , 1α
α , ×-b
a , 0β , 0a
0100s
ABS,z
Modulo 3 – U.D. 6 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 5
Grafo delle adiacenze e scelta codifiche
1
0
10110100y1
y2y3
Tabella degli stati ridondanti
β
e
d2
d1
1011
α
b
a2
a1
0100s
ABS,z
Modulo 3 – U.D. 6 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 6
Tabella degli stati ridondanti
β , 0β , 0a2 , 0β , 0β
e , 1α , 1-β , ×e
e , 1-d1 , 1d2 , 1d2
d2 , 1-α , 1d1 , 1d1
α , 1
β , 0
-
-
10
α , 1
b , 0
a1 , 0
b , 0
11
α , 1d1 , 1α
α , ×-b
a2 , 0β , 0a2
a1 , 0a2 , 0a1
0100s
ABS,z
Prosecuzione della sintesi
• Dalla tabella degli stati ridondanti, si costruiscono le tabelle delle transizioni e delle uscite.
• Dalla tabella delle uscite, si effettua la sintesi combinatoria della funzione di uscita:z = f (A, B, y1, y2 , y3)
• Dalla tabella delle transizioni, utilizzando la tabella delle eccitazioni del latch SR, si costruisce la tabella delle eccitazioni della rete.
• Dalla tabella delle eccitazioni della rete, si effettua la sintesi combinatoria delle funzioni di eccitazione:S1,R1,S2,R2,S3,R3, = f1,2,3,4,5,6 (A, B, y1, y2 , y3)
Modulo 3 – U.D. 6 – Lez. 4
Nello Scarabottolo – Architettura e reti logiche 7
Chiusura
Modulo 5 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Realizzazione dei circuiti integrati
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 1 - Introduzione alla tecnologia dell'integrazione
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Transistore bipolare
I
U
R I
UR
CC
C
EB
Modulo 5 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Transistore bipolare
Tre cristalli di silicio a contatto, con caratteristiche elettriche diverse:
• zona n con eccesso di elettroni liberi (silicio "drogato" con antimonio, fosforo o arsenico);
• zona p con penuria di elettroni liberi (silicio "drogato" con boro, gallio o indio);
• zona n con eccesso di elettroni liberi (silicio "drogato" con antimonio, fosforo o arsenico).
Realizzazione come circuito integrato. Il "drogaggio" realizzato:
• riscaldando il silicio;• esponendone la superficie a un'atmosfera di
drogante a stato gassoso.
Integrazione
1. Fotoresist sulla superficie
2. Luce per solidificare il fotoresist dove richiesto
3. Eliminazione del fotoresistdove non richiesto
4. Drogaggio
5. Rimozione del fotoresist
Modulo 5 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Integrazione
Il processo viene ripetuto più volte, per realizzare le diverse tipologie (n o p) di semiconduttore.
La miniaturizzazione è molto spinta: dimensioni lineari dell'ordine del decimo di micron.
In pochi millimetri quadrati di silicio, possono essere realizzati milioni di transistori.
Circuiti integrati
Chip Wafer
Modulo 5 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
La tecnologia dell'integrazione consente di realizzare in modo economicamente vantaggioso milioni di dispositivi integrati (transistori) su piastrine di silicio di pochi millimetri quadrati.
Il costo del singolo integrato è estremamente ridotto, una volta messo a punto il processo produttivo e il progetto elettrico.
Chiusura
Modulo 5 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Famiglie di circuiti integrati
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 1 - Introduzione alla tecnologia dell'integrazione
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Pin-out
Contatti elettrici esterni migliaia di volte piùgrandi dei dispositivi integrati (transistori).
Per ottimizzare, serve collegare direttamente sul chip molti dispositivi integrati e ridurre i contatti esterni.
Modulo 5 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
SSI
Small Scale Integration:
• alcune porte logiche in ogni chip;• 10-20 pin per chip;• ogni porta logica singolarmente accessibile;• esempi di componenti combinatori:
– 6 NOT;
– 4 2-input NAND;
– 1 8-input NOR.
• esempi di componenti sequenziali:– 2 JK flip-flop.
6 NOT
7 6 5 4 3 2 1
8 9 10 11 12 13 14
GND
Vcc
Modulo 5 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
4 2-input NAND
8 9 10
GND7 6 5
131211 14
Vcc
4 3 2 1
1 8-input NOR
8 9 10
GND
7
6 5
Vcc
4 3 2 1
1211
Modulo 5 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
2 JK flip-flop
Vcc
87 9 10 11 12
GND56 4 3 2 1
JC
K y
yC
K y
J y
MSI
Medium Scale Integration:
• alcune decine di porte logiche in ogni chip;• 10-20 pin per chip;• i componenti collegano fra loro le porte logiche
per realizzare funzioni utili in molte situazioni;• esempi di componenti combinatori:
– decoder;
– multiplexer.
• esempi di componenti sequenziali:– shift register;
– counter.
Modulo 5 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
LSI
Large Scale Integration:
• alcune migliaia di porte logiche in ogni chip;• 20-100 pin per chip;• realizzano funzioni complesse (come le varie parti
di un calcolatore):– unità centrale (di qualche anno fa …);
– gestori di periferiche (disco, video, ecc.).
• possono essere componenti programmabili:– ROM, PROM, EPROM, ...;
– PLA, PAL, ...;
– EPLD, FPGA, ....
VLSI - ULSI
Very Large (Ultra Large) Scale Integration:
• alcuni milioni di porte logiche in ogni chip;• 100-500 pin per chip;• realizzano funzioni estremamente complesse,
come:– unità centrali dei moderni calcolatori;
– memorie RAM ad alta capacità.
Modulo 5 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 6
In sintesi...
Per sfruttare la possibilità di realizzare dispositivi integrati (transistori) in spazi estremamente ridotti, serve collegare fra loro direttamente su silicio il maggior numero possibile di tali dispositivi, e minimizzare il numero di contatti elettrici verso l'esterno.
Serve individuare funzioni complesse (tanti dispositivi) e utili in molte situazioni.
Le famiglie di circuiti integrati si differenziano per il numero di dispositivi realizzati su singolo chip e per la complessità della funzione svolta.
Chiusura
Modulo 5 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Decoder
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 2 - Componenti MSI
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Decoder
Modulo 5 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Struttura del decoder
• Componente combinatorio;
• n ingressi (n = 3, n = 4);
• 2n uscite;
• il codice binario (stringa di bit) in ingresso seleziona l'uscita da attivare;
• di solito è presente un segnale (CS: Chip Select) che abilita o disabilita il funzionamento del componente.
Tabella delle verità del decoder
1
1
1
1
1
1
1
1
0
CS
00000001111
00000010011
00000100101
00001000001
00010000110
00100000010
01000000100
10000000000
00000000×××
O0O1O2O3O4O5O6O7I0I1I2
Modulo 5 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Uso del decoder
E’ un generatore di mintermini.
Una porta OR collegata alle uscite opportune può sintetizzare una qualsiasi rete combinatoria di n ingressi mediante la prima forma canonica (forma SP).
In sintesi...
Il decoder è un componente che decodifica una stringa di n bit attivando in modo selettivo l'uscita corrispondente al codice di ingresso.
Può essere usato nella sintesi combinatoria in quanto genera tutti i mintermini di una funzione a n ingressi.
La sintesi mediante prima forma canonica (SP) richiede solo la somma logica (OR) dei mintermini necessari.
Modulo 5 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 5 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Multiplexer
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 2 - Componenti MSI
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Multiplexer
Modulo 5 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Struttura del multiplexer
• Componente combinatorio;
• a ingressi di indirizzo o address(a = 2, a = 3, a = 4);
• 2a ingressi di dato;
• 1 uscita;
• il codice binario (stringa di bit) agli ingressi di indirizzo seleziona quale dato passare in uscita.
Tabella delle verità del multiplexer
1
1
1
1
1
1
1
1
0
CS
1
0
1
0
1
0
1
0
0
O
×××111
×××011
××1×01
××0×01
×1××10
×0××10
1×××00
0×××00
××××××
D0D1D2D3A0A1
Modulo 5 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Uso del multiplexer
Come descritto nella dispensa, se si deve sintetizzare una rete combinatoria a n ingressi:
• a ingressi vengono collegati agli ingressi di indirizzo del multiplexer;
• la tabella delle verità della funzione viene divisa in 2a sottotabelle;
• ad ogni ingresso del multiplexer, viene collegata una semplice rete combinatoria che realizza una delle 2a sottotabelle.
In sintesi...
Il multiplexer è un componente che consente di scegliere quale fra gli ingressi collegare all'unica uscita.
Può essere usato nella sintesi combinatoria in quanto consente di partizionare una tabella delle verità in un certo numero di sottotabelle, di più semplice realizzazione.
Modulo 5 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 5 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Shift register
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 2 - Componenti MSI
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Shift register
C
D
y
y3
3
3
3 2y
2
2
C
D 2y
1y
1
1
C
D 1y
0y
0
0
C
D 0ySerial IN
Clock
Serial OUT
Modulo 5 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Struttura dello shift register
• Componente sequenziale;
• ogni colpo di clock, i bit contenuti nei bistabilidi tipo D avanzano di una posizione;
• permette una conversione serie-parallelo;
• necessita di bistabili NON trasparenti(flip-flop) per garantire la corretta propagazione del contenuto.
Varianti dello shift register (1)
Shift register a caricamento parallelo(per conversione parallelo-serie).
C
D
y
y3
3
3
3 2y
2
2
C
D 2y
1y
1
1
C
D 1y
0y
0
0
C
D 0ySerial IN
Clock
Serial OUT
Load/Shift
Parallel IN 3 Parallel IN 2 Parallel IN 1 Parallel IN 0
Modulo 5 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Varianti dello shift register (2)
Shift register a scorrimento bilaterale(Left/Right).
Clock
DRight IN
Left/Right
y3
33
C3
y
y2
C
2D 2
2
y
1
1
C
D
y1
1yRight OUT
0y
0
C 0
D 0y
Left IN
Left OUT
In sintesi...
Lo shift register (registro a scorrimento) è un dispositivo sequenziale in grado di effettuare conversioni serie-parallelo-serie.
Può essere usato nella sintesi sequenziale per catturare gli ultimi n bit di una sequenza di ingresso e valutarne il valore.
Modulo 5 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 5 – U.D. 2 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 4 – Counter
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 2 - Componenti MSI
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Counter
1
1
C
0y
0T
y0
Q0
y
1
y
T T
1Q
2y
2
y2
Q2
3y
3T
y3
3Q
Modulo 5 – U.D. 2 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 2
Counter: diagramma temporale
0Q
1C 0
Q 10
Q 1
10
tempo
Q 103
2
1
0
Struttura del counter
• Componente sequenziale;
• a ogni colpo di clock, la configurazione binaria contenuta nei bistabili si incrementa di uno;
• può essere usato come divisore di frequenza;
• necessita di bistabili NON trasparenti(flip-flop) di tipo T.
Modulo 5 – U.D. 2 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 3
1
1
10
C
y0
y
T
y0
Q0 y
T 32
y2
y3
T
1Q Qy2
2
T
y3
Q30J
K 0
Parallel Load 0 Parallel Load 1 Parallel Load 3Parallel Load 2
Count/Load
J 1
1K
J 2
2K
J 3
3K
Varianti del counter (1)
Counter a caricamento parallelo(per conteggi a partire da valori qualsiasi).
Varianti del counter (2)
Counter bidirezionale (Up/Down)
Up/Down
C
y0
0T
0y
y1
T 1
y1
2T
y2
y2
y3
3T
y30Q Q1 Q2 Q3
Modulo 5 – U.D. 2 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
Il counter (contatore) è un dispositivo sequenziale in grado di contare gli impulsi in ingresso e di dividere la frequenza del segnale di sincronismo.
Può essere usato nella sintesi sequenziale per contare il numero di colpi di clock fra due eventi significativi.
Chiusura
Modulo 5 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Componenti ROM
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 3 - Componenti programmabili
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Obiettivi
Componenti LSI di struttura regolare, adattabili alle esigenze dell'utilizzatore.
La tecnologia adottata è legata alla maggiore o minore facilità di adattamento.
Si parla di programmabilità perché la funzione svolta dal componente può essere definita (programmata) dall'utilizzatore, con una interazione ridotta o nulla con il produttore del componente.
Modulo 5 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
ROM
I2 1I 0I
VCC
U1 U0
n=3 Ingressi m=2 Uscite
2 =8 linee di prodotton
ROM
Sezione AND:
• genera tutti i mintermini di una funzione a ningressi;
• a livello elettrico, riproduce su ogni linea di prodotto la funzione AND dei valori di ingresso, diritti o negati.
Sezione OR:
• per ogni linea di uscita, somma i mintermini ai quali rimane collegata;
• a livello elettrico, riproduce su ogni linea di uscita la funzione OR dei mintermini.
Modulo 5 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Caratteristiche della ROM
☺ Ha una struttura regolare, indipendente dalla configurazione della sezione OR.
☺ Le due sezioni AND e OR sono costituite da diodirealizzati in fase di produzione del circuito integrato, quindi estremamente affidabili.
La personalizzazione della ROM richiede l'invio alla silicon foundry della struttura della sezione OR e la produzione di circuiti integrati specifici per il singolo utilizzatore.
Eventuali errori di definizione della sezione OR richiedono la costruzione di un nuovo integrato.
PROM
I2 1I 0I
VCC
U1 U0
n=3 Ingressi m=2 Uscite
2 =8 linee di prodotton
Modulo 5 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
PROM
Sezione AND:
• identica a quella della ROM.
Sezione OR:
• i diodi sono collegati in serie a un fusibile a stato solido;
• è inizialmente completa (tutti i contatti sono realizzati).
Programmazione:
• si bruciano i fusibili dei contatti indesiderati mediante PROM Programmer.
Caratteristiche della PROM
☺ Ha una struttura regolare.
☺ Sia la sezione AND sia la sezione OR sono realizzate in modo standard dalla silicon foundry.
☺ La personalizzazione della sezione OR avviene da parte dell'utilizzatore finale.
La personalizzazione è irreversibile (bruciatura dei fusibili per i contatti da eliminare).
La presenza dei fusibili nei contatti da mantenere rallenta la propagazione dei segnali elettrici.
Modulo 5 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
EPROM
Sezione OR:• i diodi sono collegati in serie a un transistore MOS a
gate sommerso.
Programmazione:• avviene forzando cariche elettriche nel gate sommerso
mediante tensioni imposte dal PROM Programmer.
Cancellazione:• avviene mediante esposizione a luce ultravioletta.
Caratteristiche della EPROM
☺ Ha una struttura regolare.
☺ Sia la sezione AND sia la sezione OR sono realizzate in modo standard dalla silicon foundry.
☺ La personalizzazione della sezione OR avviene da parte dell'utilizzatore finale.
☺ La personalizzazione è reversibile.
La cancellazione richiede estrazione del componente dal circuito per esposizione a luce UV.
Il componente è vulnerabile a raggi solari forti o non protetti dall'atmosfera (missioni spaziali).
Modulo 5 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 6
EEPROM (E2PROM) e EAROM
Sfruttano dispositivi il cui stato può essere alterato elettricamente.
Caratteristiche:☺ Programmazione e cancellazione sono
effettuate con tensioni e correnti: i componenti possono essere programmati e cancellati "in campo" (nel circuito in cui dovranno lavorare).Cancellazione e programmazione sono operazioni lente.Il numero di cancellazioni sopportabile dal componente è limitato.
In sintesi...
• I componenti della famiglia ROM consentono la realizzazione di reti combinatorie utilizzando la prima forma canonica (SP): somma di mintermini.
• La sezione AND, fissa, realizza tutti i 2n
mintermini degli n ingressi.
• La sezione OR, programmabile, consente di scegliere quali mintermini sommare in ciascuna uscita.
• I diversi componenti si differenziano per il modo di programmare (ed eventualmente ripristinare) la sezione OR.
Vedremo perché si chiamano "memorie"...
Modulo 5 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 7
Chiusura
Modulo 5 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Componenti PLA
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 3 - Componenti programmabili
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
ROM: punti di attenzione
I componenti ROM consentono una facile realizzazione di reti combinatorie.
Ma:• la sezione AND deve generare tutti i 2n
mintermini degli n ingressi;• al crescere di n le dimensioni della sezione AND
crescono in modo esponenziale;• la sintesi come forma canonica SP non sfrutta
nessuna ottimizzazione.
Modulo 5 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
PLA
m=2 Usciten=3 Ingressi
I2
CCV
I1 I0 1U
p < 2 linee di prodotton
0U
PLA
Sezione AND:• contiene un numero di linee di prodotto
decisamente inferiore a 2n;• i collegamenti fra linee di ingresso e linee di
prodotto sono programmabili, con tecnologia a fusibile;
• ogni linea di prodotto può realizzare un implicante.
Sezione OR:• per ogni linea di uscita, somma gli implicanti ai
quali rimane collegata.
Modulo 5 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Caratteristiche della PLA
☺ Ha una struttura regolare, indipendente dalla configurazione delle sezioni AND e OR.
☺ Le due sezioni AND e OR sono entrambe programmabili mediante bruciatura dei fusibili in serie ai diodi.
☺ La sintesi è:• ottimizzata SP (implicanti);• per reti a più uscite, perché uno stesso implicante può
essere usato in più uscite (come discusso nel Modulo 2, Unità 2, Lezione 5).
L Il segnale elettrico deve attraversare DUE livelli di fusibili (AND e OR), quindi il componente risulta più lento.
In sintesi...
• I componenti PLA consentono la realizzazione di reti combinatorie utilizzando la forma ottimizzata SP: somma di implicanti.
• La sezione AND, programmabile, consente di scegliere quali implicanti realizzare.
• La sezione OR, programmabile, consente di scegliere quali implicanti sommare in ciascuna uscita.
• Lo stesso implicante può essere usato in piùuscite: sintesi ottimizzata di reti a più uscite.
Vedremo perché non si chiamano "memorie" ma "logic arrays"...
Modulo 5 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 5 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Componenti PAL
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 3 - Componenti programmabili
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
PLA: punti di attenzione
I componenti PLA consentono una realizzazione ottimizzata di reti combinatorie.
La sezione AND programmabile, tuttavia, introduce un ulteriore livello di fusibili, quindi:
• il componente risulta più lento;• il componente risulta più complesso da
programmare;• la sintesi ottimizzata per reti a più uscite non è
banale (le mappe di Karnaugh non sono di fatto utilizzabili).
Modulo 5 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
PAL
I2 1I 0I
VCC
U1 U0
n=3 Ingressi m=2 Uscite
p < 2 linee di prodotton
PAL
Sezione AND:• contiene un numero di linee di prodotto
decisamente inferiore a 2n;• i collegamenti fra linee di ingresso e linee di
prodotto sono programmabili, con tecnologia a fusibile;
• ogni linea di prodotto può realizzare un implicante.
Sezione OR:• ogni linea di uscita è collegata a priori (diodi
senza fusibili) ad alcune linee di prodotto;• ogni linea di prodotto è collegata a un'unica
uscita.
Modulo 5 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Schema della PAL
1
2
3
4
5
6
7
8
9
10
11
23
14
13
22
15
21
20
19
18
17
16
0285684
112140
168196
224252
280308
336364
392420
476448
532504
0 1 2 3 4 8 10 12 14 16 18 20 24 27
Increment
Firstfusenumbers
Dettagli schema PAL
• Ogni ingresso entra diritto e negato.
1
2 23
220
285684
0 1 2 3 4 8 10 12 14 16 18 20 24 27
Increment
Firstfusenumbers
• I fusibili (sezione AND) collegano gli ingressi alle linee di prodotto (ciascuna indicata da una piccola porta AND).
• La sezione OR fissa è indicata dalle grosse porte OR, una per ogni uscita.
Modulo 5 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Caratteristiche della PAL
☺ Ha una struttura regolare, indipendente dalla configurazione delle sezioni AND e OR.
☺ La sola sezione AND è programmabile mediante bruciatura dei fusibili in serie ai diodi.
☺ La sintesi è:
• ottimizzata SP (implicanti);
• per reti a singola uscita, perché ogni implicante ècollegato a un'unica uscita.
☺ Il segnale elettrico deve attraversare un solo livello di fusibili (AND), quindi la PAL risulta più velocedella PLA.
PAL a stadio di uscita programmabile
• Possibilità di programmare un piedino a essere ingresso o uscita, a polarità diritta o negata.
Linea prodotto
PinD Q
Mux
Linea prodottoLinea prodotto
• Possibilità di variare dinamicamente la direzione di propagazione dei segnali di uno stesso piedino (linea bidirezionale).
• Consente di realizzare reti sequenziali, sia alla Mealy sia alla Moore.
Modulo 5 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
Buffer TRI-STATE
Dispositivo la cui uscita può trovarsi in 3 stati elettrici:
• 0 a bassa impedenza;• 1 a bassa impedenza;• alta impedenza (Z).
Consente di "scollegare" il dispositivo dalla linea di uscita.
In sintesi...
I componenti PAL consentono la realizzazione di reti combinatorie utilizzando la forma ottimizzata SP: somma di implicanti.
La sezione AND, programmabile, consente di scegliere quali implicanti realizzare.
La sezione OR, fissa, usa un certo numero di implicanti per ogni uscita.
Esistono varianti delle uscite della PAL che consentono:
• di programmare un piedino come Input o Output;• di gestire linee di segnale bidirezionali;• di realizzare reti sequenziali.
Modulo 5 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 6
Chiusura
Modulo 5 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 4 – Cenni a componentiEPLD e FPGA
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 3 - Componenti programmabili
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
PAL: punti di attenzione
I componenti PAL consentono una realizzazione ottimizzata di reti combinatorie e sequenziali.
La complessità delle reti realizzabili, tuttavia, èmodesta: ingressi e uscite della rete sono collegati ai piedini del dispositivo (problema del pin-out).
Serve realizzare componenti nei quali più reti combinatorie e/o sequenziali sono connesse all'interno del dispositivo.
Modulo 5 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 2
EPLD
• Componenti programmabili in tecnologia EPROM.
• Nel componente sono presenti numeri anche elevati di semplici macrocelle.
• Una macrocella è tipicamente l'OR di 8 termini prodotto, con un bistabile D e i multiplexernecessari per programmare l'uscita.
• Le connessioni fra le macrocelle e la distribuzione del segnale di sincronismo sono realizzate con collegamenti sul chip, programmabili in modo analogo alla programmazione del comportamento delle macrocelle.
FPGA
• Simili ai componenti EPLD.
• La programmazione non viene effettuata da transistore MOS a gate sommerso, ma da un bistabile D che apre/chiude il singolo contatto.
• La programmazione richiede il caricamento iniziale dello stato aperto/chiuso di tutti i punti programmabili.
• La prototipazione risulta estremamente facilitata (basta riconfigurare il componente cambiando lo stato dei contatti errati).
• È possibile progettare sistemi che si riconfiguranodinamicamente in base alle esigenze operative (evolvable hardware).
Modulo 5 – U.D. 3 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 3
In sintesi...
Esistono componenti programmabili LSI e VLSI, che:
• consentono di realizzare reti complesse (centinaia di migliaia di porte logiche);
• mediante reti di interconnessione a bordo del chip, programmabili.
La tecnologia FPGA:• trasforma la programmazione in scrittura di bit in
bistabili;• facilita la prototipazione e la riconfigurazione;• consente di progettare sistemi capaci di
modificare la propria struttura in base alle esigenze operative.
Chiusura
Modulo 5 – U.D. 3 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 1
Esercitazione didattica
Esempi di utilizzo dei componenti programmabili
Architetture e reti logiche
Modulo 5 - Componenti elettronici integrati
Unità didattica 3 - Componenti programmabili
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Primo esempio
È dato un componente PAL a 5 ingressi, 6 linee prodotto, 2 uscite (a ciascuna delle quali sono collegate 3 linee prodotto):
• mostrare la struttura interna del componente prima della programmazione;
• mostrare come deve essere programmato e utilizzato il componente per realizzare la seguente funzione combinatoria:
f (w,x,y,z) = ∑1
(0,1,6,7,9,11,12,15)
Modulo 5 – U.D. 3 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 2
Struttura interna della PAL
V
4 3 2I II
CC
UI0I1 U1 0
Sintesi della funzione combinatoria
011010
010111
110001
001100
10110100wx
yz
f (w,x,y,z) = w x y + w x y + w x y z + w y z + w x z
f (w,x,y,z) = ( w x y + w x y + w x y z) + w y z + w x z
Modulo 5 – U.D. 3 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 3
Programmazione della PAL
VCC
Secondo esempio
È dato un componente PLA a 4 ingressi, 12 linee prodotto e 3 uscite:
• mostrare la struttura interna del componente prima della programmazione;
• mostrare come deve essere programmato il componente per realizzare le seguenti funzioni combinatorie:
f1 (w,x,y,z) = w x y + x z + y z + w x z + w z
f2 (w,x,y,z) = x z + y z + w x z + w z
f3 (w,x,y,z) = w x y + x z + y z + w x z
Modulo 5 – U.D. 3 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 4
Struttura interna della PLA
VCC
1I2I3I U1U20I U0
Programmazione della PLA
VCC
Modulo 5 – U.D. 3 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 5
Terzo esempio
Quanti fusibili sono presenti:
• in una PROM con 8 linee di ingresso e 4 di uscita;
• in una PLA con 8 linee di ingresso, 4 di uscita e 12 linee prodotto;
• in una PAL con 8 linee di ingresso, 4 di uscita e 12 linee prodotto.
Fusibili nella PROM
La sezione AND non è programmabile:• 0 fusibili
Il numero di linee prodotto è pari a 2I dove I è il numero di ingressi:
• 28 = 256 linee prodotto
La sezione OR è programmabile, e prima della programmazione presenta un fusibile per ogni incrocio fra linee prodotto e linee di uscita:
• 256 × 4 = 1024 fusibili
In totale dunque, 1024 fusibili.
Modulo 5 – U.D. 3 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 6
Fusibili nella PLA
La sezione AND è programmabile, e presenta un fusibile per ogni incrocio fra linee prodotto e linee di ingresso, sia diritte sia negate:
• 8 × 2 × 12 = 192 fusibili
La sezione OR è programmabile, e prima della programmazione presenta un fusibile per ogni incrocio fra linee prodotto e linee di uscita:
• 12 × 4 = 48 fusibili
In totale dunque, 240 fusibili.
Fusibili nella PAL
La sezione AND è programmabile, e presenta un fusibile per ogni incrocio fra linee prodotto e linee di ingresso, sia diritte sia negate:
• 8 × 2 × 12 = 192 fusibili
La sezione OR non è programmabile:• 0 fusibili
In totale dunque, 192 fusibili.
Modulo 5 – U.D. 3 – Lez. 5
Nello Scarabottolo – Architettura e reti logiche 7
Chiusura
Modulo 6 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Struttura della macchina di Von Neumann
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 1 - Macchina di Von Neumann
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Cambiamo prospettiva...
Nei moduli precedenti abbiamo analizzato:
CIRCUITI DIGITALI
• Motivi dell’affermazione• Principi di funzionamento• Modalità di progettazione (semplice)• Disponibilità sul mercato
In questo modulo consideriamo:
CALCOLATORE ELETTRONICO
• Struttura del sistema digitale più importante
CPU • Modalità di funzionamento del circuito digitale più importante
Vedremo poi come realizzare il calcolatore …
Modulo 6 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Schema della macchina di Von Neumann
CPUMemoria
di lavoro
Interfaccia
di I/O
Bus di Sistema
IN
OUT
Elementi della macchina di Von Neumann
CPUUnità master che gestisce in modo sequenziale il sistema.
Memoria di lavoroContenitore di programmi da eseguire e dati su cui operare.
Interfaccia di I/O (Input/Output)Dispositivo elettronico che consente alla CPU di dialogare con le periferiche (dispositivi di altra natura fisica).
Modulo 6 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Funzionamento della CPU (1)
Acquisisceda memoriail codicedella prossimaistruzioneda eseguire
Interpretail codiceappenaacquisito
EsegueistruzioneI0
istruzioneI1
Esegue Esegue
Inistruzione
Fase difetch
Fase didecodifica
Fase diesecuzione
CnC1C0
Funzionamento della CPU (2)
Fase di fetch:• preleva dall'esterno una stringa di bit che indica il
prossimo passo da fare (macchina programmabile);
• Esegue, quindi, uno dopo l'altro una sequenza di passi (programma).
Fase di esecuzione:• svolge quanto richiesto;
• accede all'esterno per scambiare dati.
Fase di decodifica:• interpreta la stringa di bit come istruzione macchina.
Modulo 6 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
L'esterno...Per essere programmabile, la CPU deve scoprire i propri "compiti" volta per volta.
I "compiti":• sono sequenze di stringhe di bit:
– ogni stringa un passo o istruzione;
– ogni sequenza un compito o programma.
• elaborano informazioni (dati) codificate mediante stringhe di bit.
Serve un contenitore di stringhe di bit (tante...) che possa scambiarle con la CPU rispettandone i tempi di lavoro (veloce!): MEMORIA DI LAVORO.
Struttura della memoria di lavoro
Array di "celle" contenenti ciascuna una parola.
di lavoroMemoriaLinee di
Interconnessione
Parola di memoria
i linee
d linee
1 linea
1 lineaS
L
Dati
Indirizzi
La singola cella è individuata dal proprio indirizzo.
Modulo 6 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
Interazione CPU-memoria di lavoro
La CPU segnala alla memoria:• la cella a cui è interessata (mediante l'indirizzo);• il tipo di operazione che intende svolgere:
– prelievo o Lettura del contenuto della cella;
– modifica o Scrittura del contenuto nella cella.
CPU e memoria si scambiano il contenuto della cella, secondo la direzione richiesta dalla CPU.
CPU ruolo Master: decide quando e cosa fare
Memoria ruolo Slave: risponde alle richieste della CPU
Interazione calcolatore-mondo esterno
CPU e memoria di lavoro sono autosufficienti ma misantrope...
Il mondo esterno al calcolatore non è elettronico: altri fenomeni fisici e biologici (noi...)
E’ necessario:• poter inserire in memoria di lavoro i programmi da
eseguire;
• inserire i dati da elaborare e prelevare i risultati.
Servono interfacce fra mondo elettronico del calcolatore e mondo esterno (periferia...)
Modulo 6 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 6
Struttura dell'interfaccia di I/O
DATO-OUT
INTERFACCIACONTROLLOUNITA` DI
DATO-IN
Periferica
STATO
COMANDO
Bus di Sistema
Interfaccia di I/O
Si presenta alla CPU simile alla memoria:contiene alcune "celle" o registri (COMANDO, STATO, DATO-IN, DATO-OUT).
Interagisce con la periferica secondo quanto richiesto dalla periferica stessa:
l'unità di controllo dell'interfaccia è progettata appositamenteper gestire la specifica periferica connessa.
Operazioni di lettura e scrittura nei registri diventano interazioni con il mondo esterno:
• invio di comandi alla periferica;
• conoscenza dello stato della periferica;
• scambio di dati.
Modulo 6 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 7
In sintesi...
• La CPU vive in un mondo elettronico, fatto di celle contenenti stringhe di bit.
• Da quando viene accesa a quando viene spenta, preleva in sequenza stringhe di bit e le considera operazioni da svolgere su altre stringhe di bit.
• La memoria di lavoro è il contenitore di stringhe di bit.
• Le interfacce di I/O permettono di interagire con l'esterno mediante stringhe di bit.
• Serve un collegamento elettrico (BUS, dal latino omnibus...) tra CPU e contenitori di stringhe.
• Serve definire il vocabolario (linguaggio macchina) di stringhe di bit comprensibile alla CPU.
Chiusura
Modulo 6 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Bus e spazio di indirizzamento
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 1 - Macchina di Von Neumann
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Struttura del bus
CONTROL BUS (es. linee e )
ADDRESS BUS ( linee = 2 spazio di indirizzamento)
DATA BUS ( linee = parallelismo )d d
a a
R W
UNITÀMASTER SLAVE
UNITÀ
Modulo 6 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Data Bus (bus dati)
Trasferisce "in parallelo" una stringa di bit fra Master (CPU) e Slave (Memoria o Interfaccia).
Il numero d di linee (fili) del bus:• definisce la dimensione della cella, quindi della
parola di memoria;• influisce sulle prestazioni, in quanto la banda
passante del bus (bit trasferibili per unità di tempo) cresce al crescere di d.
Ormai da tempo, d è multiplo del byte:8 bit, 16 bit, 32 bit, 64 bit, 128 bit...
Address Bus (Bus indirizzi)
Serve a indicare la cella cui la CPU intende fare riferimento.
Il numero a di linee (fili) del bus:• definisce la massima quantità 2a di celle indirizzabili,
cioè lo spazio di indirizzamento della CPU (non necessariamente pieno di memoria);
• influisce sulle potenzialità della CPU; infatti al crescere di a, crescono:– dimensione massima dei programmi eseguibili;
– quantità massima di dati elaborabili.
Ha avuto una evoluzione un po' diversa da quella del bus dati:
16 bit, 20 bit, 24 bit, 32 bit...
Modulo 6 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Control Bus (Bus di controllo)
È costituito da linee (fili) autonome, ciascuna con un proprio significato.
Alcune linee (R, W) consentono alla CPU di gestire le interazioni con i dispositivi Slave.
Altre linee (che vedremo) consentono ai dispositivi Slave di poter attivare una interazione con il Master.
Il numero di linee dipende dalla complessità della CPU, ovvero dalle sue modalità di interazione con i dispositivi Slave.
In sintesi...
• La CPU interagisce con il resto del mondo elettronico (memoria e interfacce) mediante una serie di linee parallele (BUS).
• Alcune linee:– sono dedicate al trasferimento di bit.
– sono dedicate all'indicazione della cella cui la CPU fa riferimento.
– servono a orchestrare le interazioni fra CPU e resto del mondo elettronico.
• I numeri di linee (dimensioni del bus) sono correlati alle prestazioni della CPU.
Modulo 6 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 6 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Istruzioni macchina e modi di indirizzamento
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 2 - CPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Struttura interna della CPU
General
Purpose
MemoryAddress Reg.
InstructionRegister
ProgramCounter
ConditionCodes
Control
UnitALU
Data BusAddress BusControl Bus
MAR MDRIR
PCGPRCU
A
B
C
F
R
Registers
MemoryData Register
CC
Modulo 6 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Elementi della CPU (1)
PC (Program Counter)registro che contiene l'indirizzo della cella di memoria nella quale si andrà a recuperare la prossima istruzione macchina da eseguire.
GPR (General Purpose Registers)registri di uso generale, che contengono i dati (cioè le informazioni, codificate anch'esse mediante stringhe di bit) in corso di elaborazione.
CC (Condition Codes)registro che contiene informazioni sull'esito dell'ultima elaborazione (per es.: risultato negativo, nullo, positivo).
Elementi della CPU (2)
IR (Instruction Register)registro che contiene il codice (stringa di bit) dell’istruzione in corso di esecuzione.
MAR (Memory Address Register)registro che consente alla CPU di emettere sull'Address Bus l’indirizzo della cella del dispositivo Slave che intende leggere o scrivere.
MDR (Memory Data Register)registro che consente il trasferimento di un dato dalla CPU al Data Bus durante la scrittura nei dispositivi Slave, oppure dal Data Bus alla CPU durante la lettura dai dispositivi Slave.
Modulo 6 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Elementi della CPU (3)
ALU (Arithmetic Logic Unit)• effettua tutte le elaborazioni aritmetiche (somma
in complemento a due, a volte sottrazione, moltiplicazione e divisione) e logiche (AND, OR, NOT, confronti);
• l'esito delle sue operazioni viene memorizzato nel registro CC (Condition Codes).
CU (Control Unit)• acquisisce e decodifica le istruzioni macchina
presenti in memoria di lavoro;• controlla il funzionamento di tutti gli elementi
della CPU e (mediante il bus di controllo) del resto del calcolatore (dispositivi Slave).
Set di istruzioni (ISA)
ISA (Instruction Set Architecture)• insieme di attività elementari (istruzioni) che la
specifica CPU è in grado di comprendere (decodificare) e svolgere;
• la codifica binaria delle istruzioni costituisce il linguaggio macchina della specifica CPU;
• ogni istruzione è caratterizzata da:– codice operativo (opcode) che indica di quale
istruzione si tratta;
– operandi (operands) che costituiscono i dati o le informazioni aggiuntive necessarie per eseguire l'istruzione.
Modulo 6 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Tipi di istruzioni
• Operative– richiedono alla CPU di svolgere elaborazioni sui dati,
utilizzando l'ALU (somme e sottrazioni, operazioni logiche, confronti, ecc.).
• Trasferimento– servono a prelevare da memoria di lavoro o da
interfaccia di I/O i dati su cui operare e a trasferire in memoria di lavoro o interfaccia di I/O i risultati.
• Controllo– servono a variare l'esecuzione in sequenza delle
istruzioni macchina (salti condizionati e incondizionati);
– sono l'essenza stessa della programmazione!
Modi di indirizzamento
Sono le diverse modalità di recupero dei dati necessari per l'esecuzione delle istruzioni. Es:
• Immediato– il dato è fornito nell'istruzione macchina.
• Diretto– l'istruzione macchina fornisce l'indirizzo della locazione
di memoria contenente il dato.
• Indiretto– l'istruzione macchina fornisce l'indirizzo di una cella che
contiene l'indirizzo della cella contenente il dato.
• Base+offset– l'istruzione macchina indica un registro GPR cui
sommare un offset per ottenere l'indirizzo della cella.
Modulo 6 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
In sintesi...
• La CPU esegue una dopo l'altra istruzioni macchina contenute in celle di memoria consecutive.
• Ogni istruzione specifica cosa fare (opcode) e su cosa (operands).
• Per ogni CPU, esistono diversi tipi di istruzioni, fra cui fondamentali le istruzioni di controllo del flusso di esecuzione.
• I modi di indirizzamento definiscono le modalità con cui si possono recuperare gli operandi delle istruzioni macchina.
• Le scelte progettuali relative a quanto sopra definiscono il set di istruzioni (ISA) della CPU.
Chiusura
Modulo 6 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Struttura e set di istruzioni della CPU LC-2
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 2 - CPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Struttura interna della CPU LC-2
16 bit16 bit (4+12)
16 bit
NZP (3 bit)
Control
UnitALU
Data Bus (16 bit)Address Bus (16 bit)Control Bus (2 bit)
MAR MDRIR
PCGPRCU
A
B
C
F
O
16 bit
CC
R0 (16 bit)
R1 (16 bit)
R2 (16 bit)
R3 (16 bit)
R4 (16 bit)
R5 (16 bit)
R6 (16 bit)
R7 (16 bit)
Modulo 6 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Caratteristiche della CPU LC-2 (1)
Macchina RISC(Reduced Instruction Set Computer):
• poche istruzioni macchina:– opcode 4 bit → 24=16 istruzioni.
• istruzioni macchina tutte di uguale lunghezza;• pochi modi di indirizzamento:
– immediato, diretto, indiretto, base+offset.
Macchina a 16 bit:• data bus a 16 bit → celle di memoria da 16 bit;• address bus a 16 bit → 216=64K celle di spazio di
indirizzamento.
Caratteristiche della CPU LC-2 (2)
GPR:• 8 registri a 16 bit, numerati da R0 a R7.
CC:• segno (N, Z, P) dell'ultimo valore numerico
scritto in un qualsiasi registro GPR.ALU:
• solo le operazioni strettamente indispensabili:– ADD
– AND
– NOT
Modulo 6 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
ISA della CPU LC-2
L'ISA della CPU LC-2 è descritto in dettaglio nella dispensa della lezione.
Ogni istruzione ha 4 bit di opcode e usa gli altri bit per specificare - ove necessario - gli operandi.
Poiché lo spazio destinato a ogni istruzione macchina non è sufficiente per un indirizzamento immediato o diretto a 16 bit, usa indirizzamento a pagina corrente.
Indirizzamento a pagina corrente
pgoffset9DR0111LEA
0123456789101112131415
ind16 → DR (indirizzamento immediato)
ind16 = PCMS7 & pgoffset9
• occorre costruire un indirizzo a 16 bit;
• nell'istruzione sono disponibili solo 9 bit (pgoffset9);
• concateniamo (operatore &) i 7 bit più significativi del PC (MS: Most Significant) con i 9 bit di pgoffset9;
• l'indirizzo creato appartiene alla pagina corrente (la zona di memoria di 29=512 parole nella quale si trova il programma in esecuzione, quindi alla quale "punta" il PC).
Modulo 6 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
Abbiamo una CPU didattica (LC-2) con registri a 16 bit e spazio di indirizzamento a 16 bit (216=64K celle di memoria).Il set di istruzioni è decisamente RISC:
• opcode a 4 bit (16 istruzioni);• una istruzione occupa sempre una cella di
memoria;• si opera normalmente nella pagina corrente
(individuata dal PC);• la CPU offre poche istruzioni operative, alcuni
trasferimenti (3 modi di indirizzamento) e istruzioni di controllo con supporto ai sottoprogrammi.
Chiusura
Modulo 6 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Esempi di programmi in linguaggio macchina LC-2
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 2 - CPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Esempio sui modi di indirizzamento
;programma di uso dei modi di indirizzamento;situato in memoria a partire da x30F6;usa notazione esadecimale: xEEEE;dove E=cifra esadecimale (corrisponde a 4 bit)
1 LEA R1, x30F4 ;carica 30F4 in R1
2 ADD R2, R1, x000E ;somma 14 a R1 (in R2 3102)
3 ST R2, x30F4 ;scrive R2 in 30F4
4 AND R2, R2, x0000 ;azzera R2
5 ADD R2, R2, x0005 ;inizializza R2 a 5
6 STR R2, R1, x000E ;scrive R2 in M(R1+14=3102)
7 LDI R3, x30F4 ;scrive M(M(30F4))=5 in R3
Modulo 6 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
CPU e memoria all'inizio del programma
Dopo istruzione 1
LEA R1, x30F4 ;carica 30F4 in R1
Modulo 6 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Dopo istruzione 2
ADD R2, R1, x000E ;somma 14 a R1 (in R2 3102)
Dopo istruzione 3
ST R2, x30F4 ;scrive R2 in 30F4
Modulo 6 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Dopo istruzione 4
AND R2, R2, x0000 ;azzera R2
Dopo istruzione 5
ADD R2, R2, x0005 ;inizializza R2 a 5
Modulo 6 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
Dopo istruzione 6
STR R2, R1, x000E ;scrive R2 in M(R1+14=3102)
Dopo istruzione 7
LDI R3, x30F4 ;scrive M(M(30F4))=5 in R3
Modulo 6 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 6
Esempio sulle istruzioni di controllo;programma che somma un vettore di numeri in memoria;la somma termina appena si incontra un valore nullo;programma situato in memoria a partire da x3000;vettore situato in memoria a partire da x3008
LEA R0, table ;carica 3008 in puntatore
AND R2, R2, #0 ;azzera totalizzatore
loop LDR R1, R0, #0 ;legge prossimo numero
BRZ finish ;se nullo ha finito
ADD R2, R2, R1 ;somma a totalizzatore
ADD R0, R0, #1 ;incrementa puntatore
BRNZP loop ;prossimo numero
finish ST R2, result ;scrive risultato in memoria
table ;vettore di numeri
result ;risultato
CPU e memoria all'inizio del programma
Modulo 6 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 7
Dopo la lettura del primo numero
Dopo la prima esecuzione del ciclo
Modulo 6 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 8
Termine del programma
In sintesi...
• Abbiamo visto due esempi di esecuzione di programmi in linguaggio macchina.
• Il comportamento dei due programmi è stato discusso mostrando il contenuto della CPU LC-2 e della sua memoria di lavoro.
• Abbiamo dato una rappresentazione simbolica dei programmi (con i nomi delle istruzioni LC-2 invece della loro codifica binaria).
• Abbiamo adottato sia un'analisi passo passo sia un'analisi per blocchi di istruzioni.
Vedremo gli strumenti softwareche ci consentono queste attività.
Modulo 6 – U.D. 2 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 9
Chiusura
Modulo 6 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – LinguaggioAssembly LC-2
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 3 - Supporti allo sviluppo di programmi per la CPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Motivazioni del linguaggio Assembly
• La programmazione in linguaggio macchina è estremamente scomoda e di difficile manutenzione.
• Il calcolo degli indirizzi fisici di memoria è a sua volta macchinoso e difficile.
• Ogni istruzione macchina ha un codice mnemonico definito in fase di progettazione dell'ISA.
• Anche i registri GPR hanno codici simbolici.
Definiamo un linguaggio con corrispondenza biunivoca fra istruzione mnemonica e
istruzione macchina: il linguaggio Assembly.
Modulo 6 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Struttura del linguaggio Assembly
Label riferimento simbolico scelto dal programmatore per indicare l'indirizzo di memoria dell'istruzione.
Opcode codice mnemonico dell'istruzione (ADD, JSR, ...).
Operands riferimenti simbolici a registri o indirizzi di memoria.
comments testo libero di spiegazione del significato dell'istruzione.
Esempio:
Label Opcode Operands ;comments
loop: LDR R1, R0, #0 ;legge prossimo numero
Pseudo-istruzioni: cosa sono
La traduzione da linguaggio Assembly a codice macchina viene effettuata automaticamente da un opportuno programma (Assembler).
Può essere utile fornire all'Assembler opportune direttive, che guidino tale traduzione automatica.
Le direttive si presentano come istruzioni macchina (da cui il nome pseudo-istruzioni) ma con l'Opcode preceduto dal carattere 'punto'.
Modulo 6 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Pseudo-istruzioni: quali sono
.orig consente di segnalare all'Assembler da quale indirizzo di memoria caricare il programma.
.fill consente di inizializzare con un valore costante il contenuto di una cella di memoria.
.blkw consente di riservare un certo numero di celle di memoria (per es. per contenere variabili).
.stringz consente di inizializzare una sequenza di celle di memoria con la codifica ASCII di una frase (racchiusa fra "doppi apici"). Dopo l'ultimo carattere, viene inserito il terminatore 0.
.end segnala all'Assembler il termine del programma da tradurre.
Costanti
Per inserire valori costanti, si possono utilizzare le seguenti notazioni:
Binaria bBBBBBBBBBBBBBBBB16 bit codificati come 0 o 1, preceduti dal carattere 'b'.
Esadecimale xEEEE4 cifre esadecimali (0÷9, a, b, c, d, e, f minuscole o maiuscole) precedute dal simbolo 'x'.
Decimale #DDDDDfino a 5 cifre decimali, precedute dal carattere '#', eventualmente seguito dal segno '-'.
Modulo 6 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Un esempio
.orig x3000LEA R0, table ;carica inizio tabella in punt.AND R2, R2, #0 ;azzera totalizzatore
loop LDR R1, R0, #0 ;legge prossimo numeroBRZ finish ;se nullo ha finitoADD R2, R2, R1 ;somma a totalizzatoreADD R0, R0, #1 ;incrementa puntatoreBRNZP loop ;prossimo numero
finish ST R2, result ;scrive risultato in memoriatable .blkw #4 ;vettore di numeri
.fill #0result .blkw #1 ;risultato
.end
Ritorniamo al secondo programma presentato nella Lez.3, U.D.2di questo modulo (l'esempio sulle istruzioni di controllo):
In sintesi...
• Il linguaggio Assembly: un supporto alla codifica di programmi in linguaggio macchina.
• L'Assembler: un programma di traduzione automatica da linguaggio Assembly a codice macchina.
• Le pseudo-istruzioni per guidare la fase di traduzione.
Vediamo i supporti effettivamente disponibili...
Modulo 6 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
Chiusura
Modulo 6 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Assembler LC-2 e processo di traduzione
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 3 - Supporti allo sviluppo di programmi per la CPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Codifica del programma Assembly
Strumento LC2Edit.exe in ambiente Windows.
Si installa automaticamente sul proprio PC eseguendo il file compresso lc2.exe.
Andiamo a vedere come funziona...
Modulo 6 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Traduzione del programma Assembly
È un'operazione che richiede due "passate" sul programma Assembly:
• alcune istruzioni possono essere immediatamente tradotte (es. AND R2, R2, #0);
• altre istruzioni alla prima passata non consentono la traduzione, perché mancano informazioni sul valore numerico dei simboli usati(es. LEA R0, table);
• l'Assembler crea una tabella dei simboli, che riempie nella prima passata e che usa nella seconda passata per completare la traduzione.
valuesymboltable x3008
Possibili segnalazioni di errore
Errori sintattici istruzioni o pseudo-istruzioniscritte in modo errato.
PRIMA PASSATA - compile time
Errori di simboli label citate ma non definite, oppure scritte in modo errato.
SECONDA PASSATA - link time
Errori semantici il programma non fa ciò che dovrebbe.
MAI !!!Andiamo a vedere come
funziona...
Modulo 6 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
La tabella dei simboli prodotta
// Symbol table// Scope level 0:// Symbol Name Page Address// ---------------- ------------// finish 3007// loop 3002// result 300D// table 3008
Ecco il contenuto del file .sym prodotto dall'Assembler:
In sintesi...
LC2Edit consente di:• scrivere programmi in linguaggio Assembly;• fare uso delle pseudo-istruzioni previste
dall'Assembler;• tradurre i programmi in linguaggio macchina
segnalando:– errori sintattici nella prima passata (compile time);
– errori di simboli nella seconda passata (link time).
Adesso ci serve un modo per trovare gli errori semantici: dobbiamo riuscire a eseguire (in modo
controllato) i programmi in codice macchina.
Modulo 6 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 6 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Simulatore LC-2 e processo di debugging
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 3 - Supporti allo sviluppo di programmi per la CPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Una CPU LC-2 virtuale...
Lo strumento simulate.exe in ambiente Windows simula a livello software il comportamento della (inesistente...) CPU LC-2.
Si installa automaticamente insieme a LC2Edit, discusso nella precedente lezione.
Andiamo a vedere come funziona...
Modulo 6 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Caricamento del codice macchina
Apriamo uno dei file .obj generati da LC2Edit.
Andiamo a vedere come funziona...
Esecuzione del codice macchina
Possiamo eseguire una istruzione alla volta del programma:
• la freccia blu a sinistra indica a quale cella di memoria punta il PC (quindi la prossima istruzione da eseguire);
• dopo averla eseguita, il contenuto dei registri della CPU e della memoria appaiono modificati di conseguenza;
• il bottoneStep programo il tasto F8 cifanno avanzare di una istruzione alla volta.
Andiamo a vedere come funziona...
Modulo 6 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Debugging
L'avanzamento controllato ci consente di vedere cosa fa il programma ma:
• è lento se il programma esegue numerose istruzioni (es. cicli);
• non consente di correggere errori semantici individuati: serve tornare in LC2Edit, correggere, ritradurre in codice macchina e ripartire.
lo strumento simulate, però:• consente di inserire break points (situazioni che,
quando si verificano, provocano l'arresto del programma, senza esecuzione passo passo);
• consente di modificare registri e memoria.
Andiamo a vedere come funziona...
In sintesi...
Lo strumento simulate consente di:• disporre di una CPU LC-2 (virtuale);• caricare ed eseguire passo passo un programma
in codice macchina;• effettuare il "debugging" dei programmi, cioè
andare a "spulciare" gli errori semantici che si individuano utilizzando:
– l'esecuzione passo passo;
– l'esecuzione controllata grazie alla possibilità di inserire break points;
– la possibilità di variare il contenuto dei registri e delle celle di memoria e di riprendere l'esecuzione controllata.
Modulo 6 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 6 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Programmazione interattiva
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 4 - Sviluppo di programmi per laCPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Routine di I/O
Può essere utile scrivere programmi in Assembly LC-2 che interagiscano con l'operatore.
Sono previste tre semplici routine di interazione, associate ad altrettante posizioni nel vettore di trap:
TRAP x21 emette su video il carattere il cui codice ASCII è contenuto in R0.
TRAP x23 legge un carattere da tastiera e ne riporta il codice ASCII in R0.
TRAP x25 arresta l'esecuzione del programma.
Modulo 6 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Simulazione di programmi interattivi
Se un programma fa uso delle routine di I/O:
• TRAP x21 scrittura caratteri;• TRAP x23 lettura caratteri;
si passa a LC2 Console, che simula un terminale video-tastiera interattivo.
Andiamo a vedere come funziona...
In sintesi...
Lo strumento Console consente di:• disporre di un semplice terminale interattivo a
caratteri;• costruire programmi LC-2 interattivi, che
scambiano caratteri con l'operatore durante la loro esecuzione.
La TRAP x25 (TRAP HALT) consente di arrestare l'esecuzione del programma dopo l'ultima istruzione utile.
Perché non le scrivete voi?
Non sono disponibili altre modalità di I/O: per esempio per ricevere o emettere valori numerici.
Modulo 6 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Chiusura
Modulo 6 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Esempi diprogrammi LC-2
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 4 - Sviluppo di programmi per laCPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Primo esempio: shift
La traslazione a sinistra o destra di tutti i bit di un dato corrisponde a una moltiplicazione o divisione per 2.
Costruiamo un programma che:• riceve in R0 il dato da traslare;• valuta il singolo bit di R0 (usando un valore con
un solo bit a 1 che viene ogni volta moltiplicato per 2 per "muoversi" lungo R0);
• se il bit di R0 vale 1, somma al risultato un bit spostato a sinistra (shl) o a destra (shr) di un posto;
• moltiplica per 2 il bit da sommare e ripete 16 volte.
Nell'ISA LC-2 non esiste un'istruzione di shift.
Modulo 6 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Primo esempio: modulo shift.asm
Vediamo la struttura delle due routines:
• shl trasla di un bit a sinistra il valore in R0;• shr trasla di un bit a destra il valore in R0.
Le due routines salvano e ripristinano i registri utilizzati, in modo che il programma chiamante ritrovi tutti i suoi dati intatti.
Andiamo a vedere come funziona...
Secondo esempio: modulo cmp-32.asm
Confronto fra due numeri a 32 bit (2 parole di memoria):
• si effettua il confronto fra le due parole più significative;
• se il confronto dà la soluzione (le due parole sono diverse) il programma finisce;
• se le due parole più significative sono uguali, si confrontano le due parole meno significative.
Andiamo a vedere come funziona...
Modulo 6 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Terzo esempio: modulo count-char.asm
Il programma conta quante volte il carattere immesso da tastiera compare nella stringa memorizzata:
• per evitare le difficoltà di emissione di un numero intero su video, si fa l'ipotesi che il carattere cercato non compaia più di 9 volte;
• per confrontare fra loro due valori, in assenza di istruzione macchina specifica, si fa la somma in complemento a 2 e si vede se il risultato è nullo.
Andiamo a vedere come funziona...
In sintesi...
• Alcuni esempi di programmi LC-2.Troviamo nelle dispense scaricabili dalla piattaforma una descrizione accurata del comportamento del singolo programmaistruzione per istruzione.
• La limitatezza del set di istruzioni LC-2 costringe a risolvere con algoritmi opportuni operazioni anche semplici (confronto, shift, ecc.).
• Per non alterare lo stato di esecuzione del programma chiamante, è opportuno che i sottoprogrammi salvino e ripristinino i registri GPR utilizzati.
Modulo 6 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 6 – U.D. 4 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Realizzazione dello stack per la CPU LC-2
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 4 - Sviluppo di programmi per laCPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Motivazioni
• Il meccanismo di chiamata a sottoprogramma dell'LC-2 prevede un solo livello di chiamata (usa R7 per il salvataggio del PC).
• Può essere molto utile consentire a un sottoprogramma di chiamarne a sua volta un altro.
• Serve creare una "pila" (stack) di indirizzi di ritorno: una struttura LIFO in cui l'ultimo indirizzo di ritorno inserito sarà il primo a essere prelevato.
Modulo 6 – U.D. 4 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Realizzazione
• Stack in memoria di lavoro.
• Una routine (push) che aggiunge un indirizzo di ritorno allo stack.
• Una routine (pop) che preleva il primo indirizzo di ritorno dallo stack.
• Controlli sul fatto che lo stack non sia vuoto (pop) né pieno (push).
Andiamo a vedere come funziona...
In sintesi...
• Abbiamo realizzato uno stack di indirizzi di ritorno a programma chiamante per la CPULC-2.
• Questo consente:
- l'annidamento delle chiamate;- la programmazione ricorsiva.
Modulo 6 – U.D. 4 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Chiusura
Modulo 6 – U.D. 4 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 4 – Dal linguaggio C al linguaggio Assembly LC-2
Architetture e reti logiche
Modulo 6 - Linguaggio macchina
Unità didattica 4 - Sviluppo di programmi per laCPU LC-2
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Costrutti di alto livello in Assembly
I linguaggi di alto livello si basano su astrazioni della macchina fisica:
• variabili tipizzate;• strutture di controllo evolute:
– for...
– if...then...else...
• portabilità del codice.
Il linguaggio macchina non è portabile e non ha strutture di controllo evolute.
Possiamo realizzarle in linguaggio Assembly, riportando i costrutti di alto livello come commenti.
Modulo 6 – U.D. 4 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 2
Un esempio
• Programma che calcola i numeri primi compresi fra 1 e 10.
• Codice in linguaggio C usato come commento iniziale.
• Costrutti C tradotti in linguaggio Assembly e usati come commenti.
Andiamo a vedere come funziona...
for (i=1;i<=MAXI;i++) {loop body}
;initializes i-for loop: R5=iAND R5,R5,#0 ;for (i=1;...)ADD R5,R5,#1;
checks for end of i-for looploopi LD R0,maxi ;for (...;i<=MAXi;...)
NOT R0,R0ADD R0,R0,#1ADD R0,R0,R5BRP endi
;starts body of i-for loop..... .....
;exits from i-for loopendi
Modulo 6 – U.D. 4 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 3
if (isprime==TRUE) {...}; else {...};
;checks second if conditionLD R0,isprime ;if (isprime == TRUE)BRZ elseif2
;"then" branch of second if selectionLD R0,ascii ;printf ("...prime...")..... .....BRNZP endif2
;"else" branch of second if selectionelseif2 LD R0,ascii ;printf ("...NOT prime...")
..... .....
;exits from second if selectionendif2
In sintesi...
• Con un'opportuna programmazione in linguaggio Assembly LC-2 possiamo tradurre i costrutti di controllo dei linguaggi di alto livello.
• Il software applicativo può essere tradotto in linguaggio Assembly (magari da un supporto automatico: il compilatore).
Modulo 6 – U.D. 4 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 7 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Stadi di uscita per collegamento al bus
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 1 - Collegamento al bus
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Tipi di linee di bus
Monosorgente:
• un solo dispositivo impone il valore alle linee, molti dispositivi lo acquisiscono(es. linee dell'Address Bus).
Multisorgente sincrone:
• a turno, diversi dispositivi impongono il valore alle linee (es. linee del Data Bus);
• è possibile decidere a chi tocca(sincronizzare le linee).
Multisorgente asincrone:
• diversi dispositivi impongono il valore alle linee;
• non è possibile sincronizzare i dispositivi.
Modulo 7 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Linee monosorgente
Stadio di uscita TOTEM POLE:
L'uscita può trovarsi in 2 stati:
• 0 a bassa impedenza;
• 1 a bassa impedenza.
Il dispositivo pilota SEMPRE la linea cui è collegato.
Linee multisorgente sincrone
Stadio di uscita TRI STATE:
L'uscita può trovarsi in 3 stati:
• 0 a bassa impedenza;
• 1 a bassa impedenza;
• alta impedenza (Z).
Serve un arbitro per decidere a chi tocca pilotare la linea di uscita.
Già visto nel Modulo 5, U.D.3, Lez.3
Modulo 7 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Linee multisorgente asincrone
Stadio di uscita OPEN COLLECTOR:
L'uscita può trovarsi in 2 stati:
• 0 a bassa impedenza;
• alta impedenza (Z).
Il dispositivo pilota la linea cui è collegato solo se vuole imporre il valore 0.
Se nessun dispositivo pilota la linea, serve la resistenza di pull-up per portare la linea a 1.
In sintesi...
Esistono 3 tipi di stadi di uscita, per collegare porte logiche a linee del bus:
• stadio di uscita TOTEM POLE, per una linea pilotata sempre dallo stesso dispositivo;
• stadio di uscita TRI STATE per una linea pilotata da vari dispositivi, sincronizzati fra di loro;
• stadio di uscita OPEN COLLECTOR per una linea pilotata da vari dispositivi, NON sincronizzati fra di loro.
Abbiamo già visto la necessità dei primi due tipi di stadio di uscita.
Vedremo fra poco la necessità del terzo tipo di stadio di uscita.
Modulo 7 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 7 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Chip di memoria
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 2 - Memoria di lavoro
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Memoria RAM
Alla CPU serve una memoria di lavoro elettronica (per avere tempi di risposta accettabili).
Nella memoria di lavoro devono essere inseriti dati (variabili) e codice macchina del programma volta per volta necessario (variabile).
Serve una memoria a lettura e scrittura:
• RAM (Random Access Memory): non c'è rapporto causa-effetto tra un accesso a una cella e il successivo (ogni cella è ugualmente accessibile);
•
• due tipi di dispositivi:
– SRAM (Static RAM)
– DRAM (Dynamic RAM)
Modulo 7 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Struttura della memoria SRAM (1)
Struttura della memoria SRAM (2)
Con stadi TRI STATE alle porte OR di colonna possiamo usare un Data Bus bidirezionale.
Un segnale aggiuntivo (CS: Chip Select) consente di attivare o disattivare la risposta del dispositivo.
Modulo 7 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Struttura della memoria DRAM
• Per risparmiare spazio sul chip, i bistabili sono
sostituiti da condensatori.
• Il valore del bit è associato alla carica presente sul
condensatore.
• Se il bit vale 1, dopo un certo tempo il condensatore
si scarica e "perde" l'informazione.
• È necessaria una attività periodica di refresh che
ripristini la carica sui condensatori.
• Si riescono a ottenere elevatissime densità di
memoria: chip da 1 Gbit.
Chip di RAM
• na piedini di indirizzo monodirezionali (ma);
• nd piedini di dato bidirezionali (md);
• linea di input chip select (CS);
• linea di input read/write (R/W);
• eventuale linea di input output enable (OE);
• eventuale linea di output ready (RD).
mamdCSR/WOERD
na
nd
1
1
1
1
Modulo 7 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Memoria ROM
Serve comunque una memoria a sola lettura ROM(Read Only Memory) che mantenga il proprio contenuto anche in assenza di alimentazione:
• programma da eseguire all'accensione del calcolatore (fase di bootstrap);
• situazioni nelle quali il programma da eseguire è sempre lo stesso (applicazioni embedded).
Perché una memoria ROM ha la stessa sigla di un componente combinatorio?
Sveliamo il "mistero" lasciato al termine del Modulo 5, U.D.3, Lez.1...
Reti combinatorie e memorie...
I2 1I 0I
VCC
U1 U0
n=3 Ingressi m=2 Uscite
2 =8 linee di prodotton
Modulo 7 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
Reti combinatorie e memorie...
• Gli ingressi della ROM possono essere considerati indirizzi.
• Le linee di prodotto possono essere considerate linee di parola (una per ogni configurazione degli indirizzi).
• Le linee di somma possono essere considerate linee di bit (uno per ogni uscita della ROM).
• A ogni configurazione degli ingressi, appare in uscita ciò che viene programmato nella sezione OR (una "parola" di m bit).
• Solo una sezione AND completa consente di definire liberamente il contenuto dei tutte le parole di memoria (non va bene né una PLA né una PAL).
Chip di ROM
• na piedini di indirizzo monodirezionali (ma);
• nd piedini di dato monodirezionali (md);
• linea di input chip select (CS);
• eventuale linea di input output enable (OE);
• eventuale linea di output ready (RD).
nd md
1
1
1
OERD
CS
na ma
Modulo 7 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 6
In sintesi...
Sono disponibili chip di memoria:
• a lettura e scrittura (RAM) volatili;
• a sola lettura (ROM) permanenti.
La piedinatura dei due tipi di componenti è simile:
• piedini di indirizzo;
• piedini di dato;
• piedini di controllo.
Vedremo come realizzare banchi di memoria di dimensione opportuna, a partire dai chip disponibili e sulla base delle caratteristiche della CPU considerata.
Chiusura
Modulo 7 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Banchi di memoria
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 2 - Memoria di lavoro
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Banco di memoria
• Un insieme di chip di memoria, che "riempie" una porzione dello spazio di indirizzamento della CPU considerata.
• Ogni "cella di memoria" del banco deve avere un numero di bit pari al numero di linee del Data Bus della CPU.
• Il numero di celle di memoria del banco è tipicamente una potenza di 2.
• Il banco deve "apparire" come una sequenza di celle adiacenti in una determinata posizione dello spazio di indirizzamento della CPU.
Modulo 7 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Esempio di banco di memoria
Partiamo dalla CPU LC-2:
• Address Bus a 16 linee;
• Data Bus a 16 linee.
Partiamo da chip di RAM da 1K×8:
• 1024 celle;
• da 8 bit ciascuna.
Vogliamo realizzare un banco di memoria RAM:
• da 4K celle da 16 bit;
• a partire dall'indirizzo 0000 0000 0000 0000.
Come realizzare celle da 16 bit
• Ogni componente di RAM ha celle da 8 bit.
• La CPU LC-2 pretende di "vedere" celle da 16 bit.
• Servono 2 componenti accoppiati "per riga":
– il componente di sinistra contiene gli 8 bit più significativi della cella di memoria LC-2;
– il componente di destra contiene gli 8 bit meno significativi della cella di memoria LC-2;
– il Data Bus LC-2 viene diviso in due parti: gli 8 bit più significativi vengono collegati al componente di sinistra, gli 8 bit meno significativi al componente di destra.
Modulo 7 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Come realizzare celle da 16 bit
8 md
Data Bus (DB15÷DB0)
md8
16
DB15÷DB8 DB7÷DB0
Come realizzare un banco da 4K
• Ogni coppia di componenti contiene 1K (1024) celle, individuate da una configurazione di 10 bit dell'Address Bus.
• Servono 4 coppie di componenti, per realizzare 4K (4096) celle, individuate da una configurazione di 12 bit dell'Address Bus:
– i 10 bit meno significativi dell'Address Bus (AB0÷AB9) vengono collegati a tutte le coppie di componenti;
– i 2 bit successivi (AB10,AB11) devono selezionare una coppia;
– serve un decoder (Modulo 5, U.D.2, Lez.1) collegato ai Chip Select dei componenti.
Modulo 7 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Come realizzare un banco da 4K
10 mamd8
10
8mamd
10 mamd8
10
8mamd
10 mamd8
10
8mamd
16 AB9÷AB0
CS CS
CS CS
CS CS
AB11-AB10
I1
I0
O3O2O1O0
Decoder
1 1
1
11
1
8 md1 CS
10 ma
Address Bus (AB15÷AB0)Data Bus (DB15÷DB0)
10
mdma
CS
8
1
16
DB15÷DB8 DB7÷DB0
Come posizionare il banco da 4K
• Abbiamo usato solo 12 dei 16 bit dell'Address Bus.
• I 4 bit più significativi ci dicono a quale delle 24=16 "pagine" da 4K celle ci stiamo riferendo, nello spazio di indirizzamento da 64K celle della CPU LC-2.
• Serve inserire una selezione di banco:
– se i 4 bit AB15÷AB12 assumono la configurazione associata al banco, viene abilitato il Chip Selectdel decoder;
– solo in questo caso, una riga del banco di memoria viene abilitata a interagire con la CPU.
Modulo 7 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Come posizionare il banco da 4K
10 mamd8
10
8mamd
10 mamd8
10
8mamd
10 mamd8
10
8mamd
16 AB9÷AB0
CS CS
CS CS
CS CS
AB11-AB10
I1
I0
O3O2O1O0
Decoder
1 1
1
11
1
CS
AB15÷AB12 8 md1 CS
10 ma
Address Bus (AB15÷AB0)Data Bus (DB15÷DB0)
10
mdma
CS
8
1
16
DB15÷DB8 DB7÷DB0
Segnali di controllo
• Il segnale di lettura/scrittura va distribuito a tutti i componenti di memoria, per indicare il senso del trasferimento.
• Il segnale ready va propagato alla CPU, per consentirle di sapere quando la memoria è pronta per trasferire il dato.
• In casi si realizzi un banco di memoria ROM, l'unica differenza è l'assenza del segnale di lettura/scrittura (dalla ROM si può solo leggere...).
Modulo 7 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 6
Segnali di controllo
10 mamd8
10
8mamd
10 mamd8
10
8mamd
10 mamd8
10
8mamd
16 AB9÷AB0
CS CS
CS CS
CS CS
AB11-AB10
I1
I0
O3O2O1O0
Decoder
1 1
1
11
1
CS
AB15÷AB12
R/W1 R/W1
R/W1 R/W1
R/W1 R/W1
8 md
R/W1
1 CS
10 ma
Address Bus (AB15÷AB0)Data Bus (DB15÷DB0)RW
10
mdma
CSR/W1
8
1
16
DB15÷DB8 DB7÷DB0
Attenzione alle variazioni dei segnali !
AB11-AB10
Decoder
O0O1O2O3
16Data Bus (DB15÷DB0)
I1
CSI0
AB15
WR
Address Bus (AB15÷AB0) 16
1
R/W1CSmdma10
8
1
1
10
8
R/WCSmdma
R/W
mdma
1
1
8
CS
10
R/W
mdma
1
8
1
10
CS
md
R/W1
1 CS
DB15÷DB8
ma10
8
1
1
8
10
1
8
1
10
ma
R/WCSmd
R/WCSmdma
DB7÷DB0
1
1
10
8 md
R/WCS
ma
AB9÷AB0
÷AB12
Modulo 7 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 7
Segnali di controllo diversi
DB15÷DB8
1
1CSR/W
8
10
mdma
16Data Bus (DB15÷DB0)
AB11-AB10
AB12
AB15
MemAccess
÷
O3I1
CSI0
O1O0
O2
Decoder
10
8
1
1
mamdCSR/W
10
1
8
1 R/W
ma
CSmd
md1
1CSR/W
8
10 ma
16Address Bus (AB15÷AB0) AB9÷AB0
1
R/WCS
1
mdma10
8
R/WCSmdma
1
1
8
10
CSmdma
R/W1
10
8
1
md
R/WCS
1
1
ma
DB7÷DB0
10
8
Read/Write
In sintesi...• Un banco di memoria si realizza:
– con un numero di chip per riga sufficienti a realizzare una parola di memoria della CPU;
– con un numero di righe sufficienti a fornire tutte le parole di memoria richieste.
• Il Data Bus va ripartito fra le diverse "colonne" di chip di memoria, i bit meno significativi dell'Address Bus vanno forniti a tutti i chip.
• La selezione della singola riga richiede un decoder cui collegare i bit dell'Address Bus immediatamente più significativi di quelli collegati ai chip di memoria.
• La selezione del banco richiede una rete di abilitazione del decoder, pilotata dai rimanenti bit più significativi dell'Address Bus.
Modulo 7 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 8
Chiusura
Modulo 7 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Controllodi programma
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 3 - Input/Output acontrollo di programma
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Struttura dell'interfaccia di I/O
DATO-OUT
INTERFACCIACONTROLLOUNITA` DI
DATO-IN
Periferica
STATO
COMANDO
Bus di Sistema
Ricordiamo quanto visto nella Lez.1, U.D.1 del Modulo 6:
Modulo 7 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Schema del controllo di programma
ON -> COMANDO.attesa_tasto
STATO.tasto_premuto = TRUE ?
DATO-IN -> registro_CPU
STATO.video_libero = TRUE ?
registro_CPU -> DATO-OUT
ON -> COMANDO.visualizza_carattere
START
END
SI
SI
NO
NO
Varianti del controllo di programma
In caso di più periferiche, si può decidere a programma con quale frequenza interrogare ciascuna interfaccia e quale priorità assegnarle.
Serve però un Sistema Operativo multitasking, che gestisca la ripartizione del tempo di CPU fra attività (processi o task) differenti.
Invece dei cicli di attesa, in caso di risposta NO alle due condizioni:
• STATO.tasto_premuto = TRUE ?
• STATO.video_libero = TRUE ?
si possono eseguire altre attività.
Modulo 7 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Limiti del controllo di programma
Impone al mondo esterno i ritmi della CPU (quindi dei programmi in esecuzione) in una visione tolemaica del calcolatore.
Non è adatto per fenomeni urgenti:• se la CPU è impegnata in attività onerose, può
trascurare troppo a lungo la periferica.
Non è adatto per fenomeni che si ripetono a elevata frequenza:
• ogni operazione di I/O è comunque svolta dalla CPU, che per scoprire cosa fare deve comunque acquisire da memoria mediante fasi di fetch le istruzioni macchina da eseguire.
In sintesi...
La modalità di I/O a controllo di programma è molto semplice ma:
• impone al mondo esterno i ritmi interni;• non è adeguata per fenomeni urgenti;• non è adeguata per fenomeni ripetitivi ad alta
frequenza.
Vediamo le modalità alternative.
Modulo 7 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 7 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Problematica delle operazioni di Input/Output
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 3 - Input/Output acontrollo di programma
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Collegamento CPU-interfacce di I/O
Interfacce di I/O visibili alla CPU come "celle dedicate":
• alcune "celle" trasferiscono dati;
• alcune "celle" danno comandi alla periferica o ne riportano lo stato.
Interfacce memory mapped:• le "celle dedicate" rispondono a indirizzi di
memoria;
• si possono usare le normali istruzioni macchina, ma lo spazio di indirizzamento rimane "bucato".
Interfacce I/O mapped:• alcune CPU usano uno spazio di indirizzamento
diverso, basato su istruzioni macchina dedicate.
Modulo 7 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Sincronizzazione CPU-interfacce di I/O
Ogni operazione di I/O implica la sincronizzazione fra due riferimenti temporali:
• clock della CPU;• "orologio" dei fenomeni esterni, che agiscono
sulla periferica collegata all'interfaccia.
Tre modalità di sincronizzazione:
• Direct Memory Access o DMA (indipendenti).
• interrupt (vince l'orologio);•
• controllo di programma (vince il clock);•
Controllo di programma
• La CPU esegue le operazioni di I/O quando il programma in esecuzione interagisce con l'interfaccia.
• Concettualmente "sbagliata" (sono i fenomeni esterni a dettare i tempi di lavoro) questa modalità funziona grazie alla differenza fra clock della CPU e orologio delle periferiche:
– clock estremamente veloce (GHz);
– orologio normalmente molto più lento (Hz÷kHz).
Modulo 7 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Interrupt
• La CPU esegue le operazioni di I/O quando l'interfaccia lo richiede, a seguito di quanto segnalato dalla periferica.
• Concettualmente "corretta" (sono i fenomeni esterni a dettare i tempi di lavoro) questa modalità richiede che l'interfaccia possa "interrompere" la CPU nello svolgimento delle sue attività.
• Diventa indispensabile per fenomeni "urgenti" (quando la differenza fra clock e orologio non è più tale da garantire il corretto funzionamento).
Vedremo i problemi connessicon questa interruzione.
DMA
• In alcuni casi, una operazione di I/O è costituita da molti passi singoli (es:, trasferimento di un settore da/verso memoria di massa, trasmissione/ricezione di un frame da rete).
• L'interfaccia esegue autonomamente le operazioni di I/O, e avvisa la CPU solo a lavoro finito.
Vedremo i problemi connessicon questa attività "autonoma".
Modulo 7 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
• Le operazioni di Input/Output implicano la sincronizzazione fra tempo interno (clock) ed esterno (orologio dei fenomeni legati alle periferiche).
• A seconda delle diverse frequenze dei due riferimenti temporali, dell'urgenza dei fenomeni e della loro natura, esistono tre modalità fondamentali di gestione:
– controllo di programma;
– interrupt;
– DMA (Direct Memory Access).
Chiusura
Modulo 7 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Principio di funzionamento dell'interrupt
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 4 - Input/Output ainterrupt
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Caratteristiche dell'interrupt
Consente alla periferica di segnalare la necessità di servizio alla CPU:
• serve linea dedicata del bus di controllo: INTREQ.
Ha una visione copernicana della CPU e del calcolatore rispetto al mondo esterno:
• i ritmi di lavoro sono dettati dagli eventi esterni.
Particolarmente adatto a gestire fenomeni urgenti, che non possono attendere il tempo (casuale) di interrogazione di una soluzione a controllo di programma.
Non risolve il problema dei fenomeni che si ripetono ad alta frequenza:
• ne riparliamo a proposito di DMA.
Modulo 7 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Principio di funzionamento dell'interrupt
Struttura dell'interrupt
• Richiesta di interruzione da parte della periferica (linea INTREQ del bus di controllo).
• Riconoscimento da parte della CPU al termine dell’istruzione in corso (linea INTACK).
• Salvataggio automatico da parte della CPU del PC attuale e salto alla routine di risposta all’interrupt(cioè chiamata a sottoprogramma generata dallo hardware).
• Routine di risposta che si deve preoccupare di salvare il contesto del programma interrotto.
• Al termine della risposta, ripristino del contesto (a cura della routine di risposta) e ritorno alla posizione salvata del programma interrotto.
Modulo 7 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Linea INTREQ
In un calcolatore possono esistere più periferiche che richiedono gestione a interrupt.
Non c'è possibilità di sincronizzazione fra le richieste di interrupt:
• ogni interfaccia a periferica interrompe quando la propria periferica lo richiede.
La linea di richiesta INTREQ deve essere gestita mediante porte OPEN COLLECTOR (U.D.1, Lez.1):
• linea attiva bassa;
• chi vuole interrompere forza a 0 a bassa impedenza la linea;
• normalmente la linea è tenuta a 1 dalla resistenza di pull-up.
In sintesi...
La modalità di I/O a interrupt consente alla periferica di:
• imporre i propri ritmi alla CPU;
• ottenere immediata attenzione nel caso di fenomeni urgenti.
Rimangono aperti questi problemi:
• in caso di interrupt da più periferiche, come decidere a chi dare retta;
• come riconoscere quale periferica ha richiesto interruzione;
• come decidere se e quando è opportuno che la CPU possa essere interrotta.
Modulo 7 – U.D. 4 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 7 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Interrupt cablato
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 4 - Input/Output ainterrupt
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Comportamento della CPU
La CPU è dotata delle linee INTREQ e INTACK.
Alla ricezione di un interrupt:
• salva il valore del PC;
• disabilita il riconoscimento di ulteriori interrupt;
• attiva INTACK;
• salta a un indirizzo di risposta predefinito.
La routine di risposta deve effettuare il pollingdelle interfacce:
• ogni interfaccia deve essere interrogata per sapere se è la responsabile dell'interruzione;
• l'ordine di interrogazione è associato all'urgenza della periferica.
Modulo 7 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Daisy chain
CPU Interf.1 Interf.2 Interf.n
INTREQ
INTIN
INTOUT
INTREQ
INTACK
INTOUT
INTREQ
INTIN
INTOUT
INTREQ
INTINVCC
Rpull-up
Comportamento delle interfacce
Quando una interfaccia riceve INTIN:• se non ha richiesto interrupt, propaga INTOUT;
• se ha richiesto interrupt, NON propaga INTOUT e attende di essere interrogata dalla CPU.
La priorità è associata alla posizione fisica dell'interfaccia rispetto alla CPU:
• le interfacce più vicine hanno priorità maggiore;
• la priorità non è modificabile run time.
Se una periferica ha già propagato INTOUT non può interrompere (deve attendere fine ciclo).
Se la CPU viene riabilitata a sentire gli interrupt, una periferica ad alta priorità può essere interrotta da una a bassa.
Modulo 7 – U.D. 4 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
In sintesi...
L'interrupt cablato è relativamente semplice, ma presenta i seguenti limiti:
• il polling rallenta l'inizio delle attività di risposta vere e proprie (in una fase in cui l'urgenza è fondamentale);
• la priorità delle periferiche è fissa perché dipende dalla loro posizione rispetto alla CPU;
• se la CPU non viene riabilitata agli interrupt, rimane "cieca" fino alla fine del servizio della periferica interrompente;
• se la CPU viene riabilitata agli interrupt, può essere interrotta da una periferica meno urgente di quella in servizio.
Chiusura
Modulo 7 – U.D. 4 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Interrupt vettorizzato
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 4 - Input/Output ainterrupt
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Comportamento della CPU
La CPU è dotata delle linee INTREQ e INTACK.Alla ricezione di un interrupt:
• salva il valore del PC;• disabilita il riconoscimento di ulteriori interrupt;• attiva INTACK;• attende sul Data Bus la comparsa di un
identificativo a 8 bit - inserito dall'interfaccia a periferica - che usa (come per l'istruzione TRAP) come indice in un vettore di interrupt:
– tabella di celle di memoria, una associata a ogni possibile sorgente di interrupt;
– ogni cella contiene l'indirizzo di inizio della routine di risposta all'interrupt associato.
Modulo 7 – U.D. 4 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Vantaggi e problemi
☺ Il tempo di riconoscimento della sorgente di interrupt è minimizzato:– non serve polling.
L Le interfacce a periferica si complicano:– ogni interfaccia deve essere capace di generare
il proprio identificativo sul Data Bus;– ogni interfaccia deve "sapere" il proprio
identificativo.
L Non abbiamo risolto i problemi di priorità:– se la CPU viene riabilitata a sentire gli
interrupt, può essere interrotta da chiunque.
PIC (Programmable Interrupt Controller)
• Circuito integrato di supporto alla gestione degli interrupt.
• L'interfaccia comunica al PIC la richiesta di interrupt.
• Se l'interfaccia è abilitata, il PIC attiva INTREQ.
• Quando riceve INTACK, il PIC comunica l'identificativo della periferica sul Data Bus:
– gli identificativi delle periferiche sono gestiti dal PIC, senza aggiunta di complessità per le interfacce.
• Se riceve più richieste di interrupt da diverse periferiche, dà precedenza a quella più prioritaria.
Modulo 7 – U.D. 4 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
CONTROLUNIT
I/O INTERFACEIVR
IMR
IPRCONTROLUNITPIC
CONTROLUNITCPU
CPU PIC I/O INTERFACE
Data BusAddress BusControl Bus
COMANDO
STATO
DATO-IN
DATO-OUT
Funzionamento del PIC
INTREQ
INTACK
READY
IntVect
Registri del PIC
Registri accessibili alla CPU come normali registri di interfaccia (componente programmabile):
IVR Interrupt Vector Register: contiene l'identificativo associato a ciascuna periferica collegata;
IPR Interrupt Priority Register: contiene le informazioni necessarie per stabilire l'ordine di priorità delle periferiche;
IMR Interrupt Mask Register: contiene le informazioni per sapere quali periferiche possono generare interruzioni e quali no.
Modulo 7 – U.D. 4 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
L'interrupt vettorizzato, unito all'inserimento del PIC, presenta i seguenti vantaggi:
• il riconoscimento della sorgente di interrupt è rapido senza che l'interfaccia a periferica debba essere più complessa del normale;
• la priorità delle periferiche è dinamicamente variabile;
• prima che la CPU venga riabilitata agli interrupt, si può decidere quali periferiche potranno interrompere quella in servizio riprogrammandoil registro IMR.
Chiusura
Modulo 7 – U.D. 5 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Modalità di I/O a DMA (Direct Memory Access)
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 5 - Input/Output a DMA
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Fenomeni che usano DMA
Come detto, sono spesso presenti nel calcolatore fenomeni di I/O che si ripetono ad alta frequenza:
• trasferimento di settori da/verso memoria di massa;
• trasmissione/ricezione di frames da rete.
Questi fenomeni richiedono generalmente il trasferimento da periferica a memoria o viceversa di sequenze di dati (celle).
Solo quando il trasferimento dell'intera sequenza è terminato, si può procedere con l'elaborazione.
Modulo 7 – U.D. 5 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Limiti della CPU
Anche qualora sia dedicata a questo tipo di operazioni di I/O, la CPU è penalizzata perché:
• essendo un componente general purpose, deve scoprire (fetch di istruzioni macchina) passo passocosa le si chiede di fare;
• per trasferire un dato da periferica a memoria o viceversa, il singolo accesso utile (trasferimento del dato) è penalizzato da un elevato numero di accessi "inutili":
– fetch delle istruzioni;
– incremento del puntatore all'area di memoria da/in cui trasferire i dati;
– aggiornamento del contatore di dati trasferiti...
Direct Memory Access
Questa tecnica prevede la possibilità che altri dispositivi - oltre alla CPU - possano accedere a memoria:
• diventare quindi temporaneamente Master del bus.
Per far questo, serve poter richiedere alla CPU la possibilità di utilizzare il bus:
• serve linea dedicata del bus di controllo: HOLDREQ.
Anche gli stadi di uscita della CPU che pilotano le linee dell'Address Bus e del Control Bus devono essere TRI STATE (per lasciare agli altri Master la possibilità di pilotarle).
Modulo 7 – U.D. 5 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Linea HOLDREQ
In un calcolatore possono esistere più periferiche che richiedono DMA.
Non c'è possibilità di sincronizzazione fra le richieste di DMA:
• ogni gestore di DMA chiede i bus quando la propria periferica deve trasferire un dato.
La linea di richiesta HOLDREQ deve essere gestita mediante porte OPEN COLLECTOR (U.D.1, Lez.1):
• linea attiva bassa;
• chi vuole i bus forza a 0 a bassa impedenza la linea;
• normalmente la linea è tenuta a 1 dalla resistenza di pull-up.
DMAC (DMA Controller)
Integrato di supporto alla gestione del DMA.La CPU programma il DMAC comunicando:
• indirizzo della zona di memoria da/in cui trasferire i dati;
• numero di dati da trasferire;• identificativo della periferica e senso di
trasferimento.Quando la periferica segnala di essere pronta:
• il DMAC richiede i bus con il segnale HOLDREQ;• quando la CPU ne ha terminato l'eventuale uso in
corso, ne segnala il rilascio con HOLDACK;• il DMAC effettua il trasferimento e aggiorna
puntatori e contatori;• finito l'intero trasferimento, genera interrupt.
Modulo 7 – U.D. 5 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Funzionamento del DMAC
CONTROLUNIT
I/O INTERFACEMDA
DC
PACONTROLUNITDMAC
CONTROLUNITCPU
CPU DMAC I/O INTERFACE
TD
Memoria
Data BusAddress BusControl Bus
COMANDO
STATO
DATO-IN
DATO-OUT
READY
HOLDREQHOLDACK S
IN
DataINTREQINTACK
Address
Registri del DMAC
Registri accessibili alla CPU come normali registri di interfaccia (componente programmabile):
PA Peripheral Address: contiene l'identificativo dell'interfaccia a periferica con cui interagire per scambiare i dati;
MDA Memory Data Address: contiene l'indirizzo della prossima cella di memoria in cui inserire o da cui prelevare il dato;
DC Data Counter: contiene il numero di dati ancora da trasferire;
TD Transfer Direction: indica se l'operazione è una lettura (IN) o una scrittura (OUT).
Modulo 7 – U.D. 5 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
In sintesi...
La tecnica di I/O mediante DMA ha le seguenti caratteristiche:
• è possibile trasferire dati da/verso la memoria sotto il controllo di un componente diverso dalla CPU;
• tale componente - il DMAC - ha il vantaggio di essere realizzato a questo scopo, e non perde tempo per scoprirlo da programma;
• il trasferimento avviene in modo "trasparente" al programma in esecuzione sulla CPU (che viene semplicemente rallentata perché deve occasionalmente rilasciare i bus);
• al termine dell'intera attività, il programma che aveva richiesto I/O viene avvisato con interrupt.
Chiusura
Modulo 7 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Comportamento HW/SW durante I/O in DMA
Architetture e reti logiche
Modulo 7 - Architettura del calcolatore
Unità didattica 5 - Input/Output a DMA
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Esempio: lettura di un settore da disco
Il programma in esecuzione da parte della CPU richiede la lettura di un settore (1 Kbyte) da memoria di massa a disco.
Il calcolatore in esame è dotato di DMAC per le operazioni di I/O su disco.
Vediamo il comportamento dei 3 attori coinvolti:
• CPU (attività software in blu, hardware in verde)
• DMAC (attività in rosso)
• Interfaccia a disco (attività in marrone)
Modulo 7 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Attivazione I/O
• Il programma in esecuzione chiama la routine readisk del Sistema Operativo;
• La routine readisk inizializza il DMAC:
– inserisce in PA l'identificativo dell'interfaccia;
– inserisce in MDA l'indirizzo della zona di memoria che fa da buffer del disco;
– inserisce in DC il valore 1024 (n° byte da leggere);
– inserisce in TD l'indicazione di lettura (IN).
• La routine readisk inizializza l'interfaccia:
– comunica il numero della traccia e del settore da leggere da disco, indica che si tratta di lettura.
• Il S.O. sospende il programma in esecuzione e lancia altre attività.
Trasferimento di ciascun byte
• L'interfaccia segnala dato pronto al DMAC.
• Il DMAC chiede i bus alla CPU (HOLDREQ).
• La CPU rilascia i bus (HOLDACK).
• Il DMAC:
– pone su Address Bus il contenuto di MDA;
– dà il segnale IN all'interfaccia e S alla memoria:
⇒ un dato viene scritto direttamente da interfaccia a memoria, mediante il Data Bus;
– incrementa MDA e decrementa DC;
– toglie la richiesta dei bus (HOLDREQ).
• La CPU disattiva HOLDACK e si riappropria dei bus.
Modulo 7 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Dopo il trasferimento dell'ultimo byte
• Il DMAC genera una interruzione.
• La CPU riconosce l'interruzione e attiva la routine di risposta all'interrupt di DMAC.
• La routine di risposta all'interrupt segnala a readisk che l'operazione è finita (per es. forzando a TRUE un opportuno flag).
• Il S.O. riattiva il programma che aveva richiesto la lettura del settore da disco, e che a questo punto può riprendere le proprie attività.
In sintesi...
• La tecnica di I/O mediante DMA implica una sequenza di attività HW e SW che coinvolgono:
– CPU;
– DMAC;
– Interfaccia di I/O.
• Il trasferimento sfrutta l'efficienza del DMAC, progettato ad hoc per trasferire tabelle di dati.
• Il trasferimento del singolo byte comporta semplicemente un'attesa nell'uso dei bus da parte della CPU.
• La percezione a livello SW dell'attività si ha solo a trasferimento terminato, mediante interrupt.
Modulo 7 – U.D. 5 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 8 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Data Pathdi una semplicissima CPU
Architetture e reti logiche
Modulo 8 - Struttura della CPU
Unità didattica 1 - Struttura interna della CPU
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
La CPU NS-0
Per analizzare in dettaglio la struttura interna di una CPU ci rifacciamo a un esempio didattico estremamente semplice:
la CPU NS-0
...cioè la CPU di Nello Scarabottolo, che non è neppure arrivata alla versione 1 perché l'autore si vergogna di proporla al vasto pubblico...
Modulo 8 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Caratteristiche della CPU NS-0 (1)
Macchina RISC...hissima!(Reduced Instruction Set Computer):
• pochissime istruzioni macchina:– opcode 2 bit → 22=4 istruzioni.
• istruzioni macchina NON tutte di uguale lunghezza;
• pochissimi modi di indirizzamento:– immediato e diretto.
Macchina a 16 bit:• data bus a 16 bit → celle di memoria da 16 bit;• address bus a 14 bit → 214=16K celle di spazio di
indirizzamento.
Caratteristiche della CPU NS-0 (2)
GPR• 1 registro a 16 bit, denominato con molta
fantasia R0...CC
• eventuale valore nullo (Z) dell'ultimo risultato di un'operazione di somma da parte dell'ALU.
ALU• solo le operazioni strettamente indispensabili:
– ADD
– ...basta...
Modulo 8 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
ISA della CPU NS-0
ind1400LOAD
0123456789101112131415
M(ind14) → R0
ind1410STORE
0123456789101112131415
R0 → M(ind14)
val16
0000000000000001ADD
0123456789101112131415
R0 + val16 → R0
ind1411BRZ
0123456789101112131415
if (Z ≠ 0) then ind14 → PC
Struttura interna della CPU NS-0
MAR
MDR
IR
PC
R0 (16 bit)
CU
A
B
C
F
O
Z (1 bit)
Input
Inte
rnal
Bus
Outp
ut1
Inte
rnal
Bus
Outp
ut2
Inte
rnal
Bus
GPR
CC
14 bit
16 bit (2+14)
14 bit
16 bit
ALU
Data Bus (16 bit)Address Bus (14 bit)Control Bus (2 bit)
Modulo 8 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Registri della CPU NS-0
Input
Inte
rnal
Bus
Outp
ut1
Inte
rnal
Bus
INR OUT1R
Rn-1 n-2R1
R0
RD
C
Q QD
C
QD
C
QD
C
Registro MDR della CPU NS-0
INMDR OUT1
MDRMDR
SAMPLE MDROE
Data Bus
MDRn-1 0MDR
D
C
Q QD
C
Input
Inte
rnal
Bus
Outp
ut1
Inte
rnal
Bus
Modulo 8 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
Scopo degli Internal Bus: il Data Path
Un registro può:• emettere il suo contenuto sugli Output Internal Bus cui è
collegato; • campionare il valore presente sull'Input Internal Bus.
Se l'ALU è capace di propagare alla sua uscita O ciò che si presenta a uno degli ingressi A o B, le informazioni possono circolare fra i registri della CPU:
Comando ALU (C) SignificatoMSB LSB
0 0 NOP0 1 PASS (O=A)1 0 INC (O=A+1)1 1 ADD (O=A+B) (if O=0: 1→F)
Abbiamo definito il DATA PATH.
Comandi ai registri
Per muovere i dati lungo il Data Path, oltre ai comandi all'ALU ci servono i seguenti comandi per i registri:
ZSAMPLE
R0IN , R0OUT1 , R0OUT2
PCIN , PCOUT1
IRIN , IROUT1
MARIN , MAROE
MDRIN , MDROUT1 , MDRSAMPLE , MDROE
Modulo 8 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 6
In sintesi...
In una CPU particolarmente semplice, abbiamo definito il Data Path:
• tre Internal Bus per far circolare i valori presenti nei registri della CPU;
• ALU per collegare i due Internal Bus di Output all'Internal Bus di Input;
• comandi per estrarre il contenuto di ciascun registro o per modificare il contenuto di ciascun registro;
• comandi per emettere il contenuto di MAR sull'Address Bus e per scambiare il contenuto di MDR con il Data Bus;
• comandi MEMR e MEMW del Control Bus per accedere a memoria.
Chiusura
Modulo 8 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Control Pathdi una semplicissima CPU
Architetture e reti logiche
Modulo 8 - Struttura della CPU
Unità didattica 1 - Struttura interna della CPU
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Il Control Path
Abbiamo visto nella lezione precedente quali comandi abbiamo per "orchestrare" i trasferimenti di dati (Data Path) nella CPU NS-0.
Vediamo ora come controllare tali trasferimenti (Control Path).
Nella prossima U.D., discuteremo le possibili strutture circuitali in grado di gestire il suddetto Control Path:
tali strutture circuitali sono i diversi modi in cui possiamo affrontare il progetto della CU.
Modulo 8 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Fase di fetch
step comandi
s0 PCOUT1 , ALUPASS , MARIN
s1 MAROE , MEMR , ALUNOP
s2 MAROE , MEMR , MDRSAMPLE , ALUNOP
s3 MDROUT1 , ALUPASS , IRIN
s4 PCOUT1 , ALUINC , PCIN
S0: PCOUT1 , ALUPASS , MARIN
MAR
MDR
IR
PC
R0 (16 bit)
CU
A
B
C
F
O
Z (1 bit)
Input
Inte
rnal
Bus
Outp
ut1
Inte
rnal
Bus
Outp
ut2
Inte
rnal
Bus
GPR
CC
14 bit
16 bit (2+14)
14 bit
16 bit
ALU
Data Bus (16 bit)Address Bus (14 bit)Control Bus (2 bit)
Modulo 8 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
S1: MAROE , MEMR , ALUNOP
MAR
MDR
IR
PC
R0 (16 bit)
CU
A
B
C
F
O
Z (1 bit)
Input
Inte
rnal
Bus
Outp
ut1
Inte
rnal
Bus
Outp
ut2
Inte
rnal
Bus
GPR
CC
14 bit
16 bit (2+14)
14 bit
16 bit
ALU
Data Bus (16 bit)Address Bus (14 bit)Control Bus (2 bit)
S2: MAROE , MEMR , MDRSAMPLE , ALUNOP
MAR
MDR
IR
PC
R0 (16 bit)
CU
A
B
C
F
O
Z (1 bit)
Input
Inte
rnal
Bus
Outp
ut1
Inte
rnal
Bus
Outp
ut2
Inte
rnal
Bus
GPR
CC
14 bit
16 bit (2+14)
14 bit
16 bit
ALU
Data Bus (16 bit)Address Bus (14 bit)Control Bus (2 bit)
Modulo 8 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
S3: MDROUT1 , ALUPASS , IRIN
MAR
MDR
IR
PC
R0 (16 bit)
CU
A
B
C
F
O
Z (1 bit)
Input
Inte
rnal
Bus
Outp
ut1
Inte
rnal
Bus
Outp
ut2
Inte
rnal
Bus
GPR
CC
14 bit
16 bit (2+14)
14 bit
16 bit
ALU
Data Bus (16 bit)Address Bus (14 bit)Control Bus (2 bit)
S4: PCOUT1 , ALUINC , PCIN
MAR
MDR
IR
PC
R0 (16 bit)
CU
A
B
C
F
O
Z (1 bit)
Input
Inte
rnal
Bus
Outp
ut1
Inte
rnal
Bus
Outp
ut2
Inte
rnal
Bus
GPR
CC
14 bit
16 bit (2+14)
14 bit
16 bit
ALU
Data Bus (16 bit)Address Bus (14 bit)Control Bus (2 bit)
Modulo 8 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Fase di decodifica
In base all'opcode acquisito nella fase di fetch(i due bit più significativi del registro IR) si decide quale tra le 4 istruzioni macchina dell'ISA NS-0 deve essere eseguita.
Il prossimo step (s5) sarà dunque il primo di una delle 4 istruzioni.
Fase di exec: LOAD
step comandi
s5 IROUT1 , ALUPASS , MARIN
s6 MAROE , MEMR , ALUNOP
s7 MAROE , MEMR , MDRSAMPLE , ALUNOP
s8 MDROUT1 , ALUPASS , R0IN
Modulo 8 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 6
Fase di exec: STORE
step comandi
s5 IROUT1 , ALUPASS , MARIN
s6 R0OUT1 , ALUPASS , MDRIN
s7 MAROE , MEMW , MDROE , ALUNOP
s8 MAROE , MEMW , MDROE , ALUNOP
Fase di exec: ADD
step comandi
s5 PCOUT1 , ALUPASS , MARIN
s6 MAROE , MEMR , ALUNOP
s7 MAROE , MEMR , MDRSAMPLE , ALUNOP
s8 PCOUT1 , ALUINC , PCIN
s9 MDROUT1 , R0OUT2 , ALUADD , R0IN , ZSAMPLE
Modulo 8 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 7
Fase di exec: BRZ
step comandi
s5 if (Z=1) IROUT1 , ALUPASS , PCIN
In sintesi...
In una CPU particolarmente semplice, abbiamo definito il Control Path:
• sequenza di comandi all'ALU, ai registri, al Control Bus per svolgere le varie fasi di esecuzione di una istruzione macchina;
• la fase di fetch è comune a tutte le istruzioni, e usa i suddetti comandi;
• la fase di decodifica richiede di scegliere quali passi svolgere in funzione dell'istruzione acquisita durante il fetch;
• la fase di esecuzione usa di nuovo gli stessi comandi visti sopra.
Andiamo a vedere come è fatta la CU.
Modulo 8 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 8
Chiusura
Modulo 8 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – CU cablata
Architetture e reti logiche
Modulo 8 - Struttura della CPU
Unità didattica 2 - Struttura della Control Unit (CU)
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
I/O della CU
Input• opcode dell'istruzione acquisita durante il fetch
(L, S, A, B);• situazione del registro CC (Z on/off);• stato di avanzamento (n° dello step da eseguire).
Output• comandi ai registri;• comandi all'ALU;• comandi al Control Bus.
Modulo 8 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Struttura della CU cablata
BASL
IR15 14
decoder
CCZ
counter
decoder
Clock
S9 S8 S7 S6 S5 S4 S3 S2 S1 S0
comandi a registri, ALU, Control Bus (Output CU)
Approccio hardware
Ogni Output è attivo in determinati step di esecuzione.
Costruiamo una espressione logica (combinatoria) degli Output come funzione degli Input elencati in precedenza.
Realizziamo il circuito come Logic Array (una PLA che però non richiede di essere programmata, ma realizzata ad hoc, quindi senza i problemi di scarsa velocità legati ai fusibili).
Modulo 8 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Alcune espressioni logiche
PCOUT1 = S0 + S4 + (S5+S8)·A
MAROE = S1 + S2 + S6·(L+A) + S7·(L+S+A) + S8·S
IROUT1 = S5·(L+S+B·Z)
...
ALUMSB = S4 + (S8+S9)·A
ALULSB = S0 + S3 + S5·(L+S+A+B·Z) + S6·S + S8·L + S9·A
MEMR = S1 + S2 + (S6+S7)·(L+A)
...
Caratteristiche della CU cablata
☺ Una struttura particolarmente efficiente.
☺ Assicura la massima velocità di esecuzione.
☺ Particolarmente adatta a CPU RISC:
motivo del successo iniziale dell'approccio RISC.
L Di difficile modifica.
L Di difficile utilizzabilità per macchine CISC, per l'esplosione della complessità del LogicArray.
L Solo recentemente, grazie all'evoluzione tecnologica, è applicabile a CU complesse.
Modulo 8 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
• Abbiamo visto un approccio hardware alla realizzazione della CU: la CU cablata.
• L'approccio si rivela ottimo per CPU RISC, dove il ridotto set di istruzioni implica una CU semplice, meno per CPU CISC, per le quali la CU cablata diventa molto più complessa.
• Con una tecnologia elettronica non particolarmente sofisticata - come quella degli anni 1980 - si richiede dunque un approccio alternativo alla realizzazione di CU complesse.
Chiusura
Modulo 8 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – CU microprogrammata
Architetture e reti logiche
Modulo 8 - Struttura della CPU
Unità didattica 2 - Struttura della Control Unit (CU)
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
I/O della CU
Input• opcode dell'istruzione acquisita durante il fetch
(L, S, A, B);• situazione del registro CC (Z on/off).
Output• comandi ai registri;• comandi all'ALU;• comandi al Control Bus.
Modulo 8 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Struttura della CU microprogrammata
memoria dimicroprogramma
microistruzione
microprogramcounter
generatoredel prossimo
indirizzo
microcomandi prossimo indirizzo condizionidi salto
comandi a registri, ALU, Control Bus (Output CU)
Z ( )CC
IR15 14
IR
Approccio software
Ogni Output è attivo in determinate microistruzioni del microprogramma che guida il comportamento della CU.
Costruiamo una memoria di microprogramma (tipicamente una ROM) che contiene le sequenze di passi.
Per ramificare il flusso di esecuzione del microprogramma (fase di decodifica, salti condizionati, ecc.) inseriamo una logica di salto che decide la prossima microistruzione da eseguire.
Modulo 8 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Microprogramma
mA MAR MDR IR PC R0 Z ALU MEM J JNZ J15 J14 mAIN OE IN OUT1 S A M OE IN OUT1 IN OUT1 IN OUT1 OUT2 S A M M SB LSB R W
FETCH 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 01 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 02 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 03 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 04 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 105 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 15
LOAD 6 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 07 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 08 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 09 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 010 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 20
STORE 11 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 012 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 013 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 014 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0
ADD 15 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 016 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 017 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 018 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 019 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 0
BRZ 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 021 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0
Caratteristiche della CU microprogrammata
☺ Una struttura particolarmente regolare.
☺ Particolarmente adatta a CU complesse (CISC) con tecnologia hardware non evoluta.
☺ Sfrutta le tecniche di progettazione software.
☺ Molto utilizzata negli anni 1980.
L Problemi di velocità di esecuzione dovuti alla presenza della memoria di microprogramma.
L Soppiantata da un approccio cablato quando la tecnologia di integrazione lo consente.
Modulo 8 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
• Abbiamo visto un approccio software alla realizzazione della CU: la CU microprogrammata
• L'approccio si rivela ottimo per CPU CISC, perché consente di gestirne la complessità, meno per CPU RISC, penalizzate dalle scarse prestazioni della CU microprogrammata.
• Con una tecnologia elettronica non particolarmente sofisticata - come quella degli anni 1980 - è l'approccio vincente alla realizzazione di CU complesse.
Chiusura
Modulo 8 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Compiti e organizzazione dell'ALU
Architetture e reti logiche
Modulo 8 - Struttura della CPU
Unità didattica 3 - Struttura dell'ALU(Arithmetic Logic Unit)
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Compiti dell'ALU
Come visto nell'U.D.1, l'ALU deve:• provvedere a chiudere il Data Path fra i vari bus
interni della CPU;
• svolgere operazioni logiche sugli operandi A e B:– AND bit a bit;
– OR bit a bit;
– NOT bit a bit.
• svolgere operazioni aritmetiche sui numeri A e B:– confronti;
– somme (e sottrazioni) in complemento a due;
– a volte moltiplicazioni e divisioni.
Modulo 8 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Struttura dell'ALU
• A e B: ingressi operandi (parallelismo della CPU);• R: risultato (parallelismo della CPU);• C: comando (2C = numero di operazioni
disponibili);• F: flag di esito (una per ogni condizione
verificata).
ALU
A
B
C
F
R
Struttura interna dell'ALU
Modulo 8 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Struttura interna dell'ALU
Rete combinatoria che:• in base al comando (C) inviato,• opera sugli operandi A e B,• per produrre il risultato R,• e le flag di esito F.
Può avere comportamento sequenziale in alcune sue componenti (es. moltiplicatore) ma
all'esterno presenta comunque un comportamento combinatorio.
In sintesi...
• L'ALU è una rete combinatoria (o con comportamento esterno combinatorio) che effettua le reali elaborazioni (trasformazioni) di informazioni nel calcolatore.
• Opera in base al comando ricevuto, e produce un risultato e alcune flag di indicazione dell'esito dell'operazione (segno del risultato, errori aritmetici, ecc.).
Analizziamo come sono realizzate alcune funzioni fondamentali dell'ALU.
Modulo 8 – U.D. 3 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Chiusura
Modulo 8 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Circuiti sommatori
Architetture e reti logiche
Modulo 8 - Struttura della CPU
Unità didattica 3 - Struttura dell'ALU(Arithmetic Logic Unit)
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
A B
S
R HA
Somma di 2 numeri a 1 bit
Abbiamo già visto, nel Modulo 1, U.D.3, L.3:• il circuito HALF ADDER;• il circuito FULL ADDER.
FAR
S
A B
R
1 1
1
1
2
Modulo 8 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Somma di 2 numeri a n bit
Ogni FA è una rete combinatoria a 2 livelli.
Per la somma di 2 numeri a n bit servono n FA.
La rete risultante è una rete a 2n livelli (lenta).
FA
S1
1R
BA 11
FA
S0
BA0 0
R
2S
2
FA3R
A B2 2
R
n-1S
n-1
FAnR
A Bn-1 n-1
Carry look ahead - espressione logicaEspressione logica del riporto (i+1)esimo:
Ri+1 = AiRi + BiRi + AiBi
Fattorizziamo nel modo seguente:Ri+1 = AiBi + (Ai + Bi)Ri
ovvero: Ri+1 = Gi + PiRi
dove: Gi = AiBi Generate function
Pi = Ai + Bi Propagate function
Iterando: Ri+1 = Gi + PiGi-1 + PiPi-1Ri-1
Ri+1 = Gi + PiGi-1 + PiPi-1Gi-2 +
+ PiPi-1...P1G0 + PiPi-1...P0R0
Modulo 8 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Carry look ahead - circuito
Il riporto (i+1)esimo è una rete a 3 livelli che usa:
• una somma di prodotti (2 livelli);• i cui termini sono somme o prodotti dei bit di
dato (3° livello).
Si può dunque anticipare il riporto ("guardare avanti" il riporto) nei limiti della complessità di una rete combinatoria con porte logiche a tanti ingressi:
circuiti di CLA usuali: 8 bit o meno.
Sommatore/sottrattore in complemento a 2
Una batteria di porte XOR e un segnale ADD/SUB consentono di effettuare il complemento a 2 "on the fly".
Il circuito risultante esegue sia la somma sia la differenza in complemento a 2.
SSn-1 2
A
B
A
B
FARn n-1R
n-1
n-1
FA3R 2R
2
2
SS1 0
A
BB
A
FAFAR1
1
1 0
0
ADD/SUB
Modulo 8 – U.D. 3 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
• I circuiti sommatori basati su FA hanno il problema del ritardo di propagazione del riporto (carry).
• Con opportune reti a 3 livelli (carry look ahead) riusciamo ad anticipare il calcolo del riporto e a velocizzare la somma.
• Un semplice artificio consente di ottenere anche il circuito sottrattore, a patto di adottare la codifica dei numeri in complemento a 2.
Chiusura
Modulo 8 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 3 – Circuiti moltiplicatori
Architetture e reti logiche
Modulo 8 - Struttura della CPU
Unità didattica 3 - Struttura dell'ALU(Arithmetic Logic Unit)
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Esecuzione della moltiplicazione a n bit
Prodotto P (143)11110001
1011
0000
1011
1011
Moltiplicatore Q (11)1101×
Moltiplicando M (13)1011
Modulo 8 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Regola di calcolo
Si costruisce la matrice diagonale dei prodotti parziali:
• dove il moltiplicatore vale 1, si copia il moltiplicando;
• dove il moltiplicatore vale 0, si inseriscono zeri.
Si effettua la somma per colonna dei prodotti parziali.
Ad ogni generazione di riporto, si scrive un uno nella colonna immediatamente più significativa (a sinistra).
Matrice di calcolo
Ogni elemento della matrice deve calcolare il prodotto parziale:
• bit del moltiplicando AND bit del moltiplicatore.
I bit del moltiplicatore si devono propagare per riga.
I bit del moltiplicando si devono propagare in diagonale.
Ogni elemento della matrice deve:
• sommare il prodotto parziale con il risultato parziale della somma in colonna;
• tenere conto del riporto in ingresso;
• generare l'eventuale il riporto in uscita.
Modulo 8 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Schema circuitale della cella
jm
FA
qi
R in
ppi+1
qi
Rout
mj
ppi
Schema circuitale della matrice
m3 m2 m1 m0
q 0
q 1
q 2
q 3
0 0 0 0
0
0
0
0
0p
p 1
p 2
p 3p 4p 5p 6p 7
Modulo 8 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Propagazione dei segnali
La generazione dei prodotti parziali richiede 1 livello di porte logiche (AND).
Ogni cella introduce ulteriori 2 livelli (circuito FA: FULL ADDER).
Dopo aver completato la prima riga della matrice diagonale (n celle) i riporti devono discendere lungo la diagonale (n-1 celle).
Il numero di livelli totali da attraversare per produrre il risultato è dunque:
NLIVELLI = 1 + 2 × (n + (n-1)) = 4n - 1
In sintesi...
• Il prodotto di 2 numeri da n bit può essere fatto con una rete combinatoria di n×n celle, ciascuna contenente una porta AND e un FULL ADDER.
• Il ritardo di calcolo totale è pari al tempo di attraversamento di 4n-1 livelli di porte logiche.
• La complessità del moltiplicatore cresce con il quadrato del numero di bit dei fattori.
Abbiamo completato il nostro percorso:dal bit al calcolatore elettronico!
Modulo 8 – U.D. 3 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
Chiusura
Modulo 9 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Principio di funzionamento della memoria cache
Architetture e reti logiche
Modulo 9 - Principali linee di evoluzione architetturale
Unità didattica 1 - Memoria cachee gerarchia di memoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Un grafico di qualche anno fa...
750
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
20
40
60
80
100
120
140
160
MHz
anno
CPU
DRAM
80888086 286 386
486
Pentium
Pentium (100 MHz)
Modulo 9 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
C'è qualcosa che non torna...
• A partire dal 1982, la frequenza di lavoro delle CPU della famiglia i86 cresce decisamente più della frequenza di lavoro dei chip di DRAM (cioè dei costituenti la memoria di lavoro).
• Verso la fine degli anni '90, il gap è di un ordine di grandezza (un fattore 10).
Come è possibile che i PC funzionasserocon una memoria di lavoro
10 volte più lenta della CPU ???
Cosa serve davvero alla CPU?
x0000
xFFFF
indirizzo generato dalla CPU
tempo
Modulo 9 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Principio di località
Se all'istante t la CPU genera l'indirizzo di memoria xNNNN, è molto probabile che nell'immediato futuro generi di nuovo lo stesso indirizzo xNNNN o indirizzi vicini ("locali") all'indirizzo xNNNN.
• Località spaziale:– il fetch delle istruzioni procede in celle consecutive;
– i programmi sono organizzati in moduli, con le variabili del singolo modulo memorizzate vicine.
• Località temporale:– l'essenza della programmazione sono i cicli: istruzioni e
variabili usate nei cicli vengono "ripassate".
Sfruttiamo il principio di località
Lavoriamo su base statistica.
Quando la CPU genera un indirizzo di memoria, portiamo il contenuto della cella richiesta e un certo numero di celle vicine (blocco) in una memoria:
• più veloce della DRAM;• ovviamente più piccola, perché più costosa da
realizzare.
Chiamiamo questa memoria cache:• deriva dal francese caché (nascosto) perché la
sua esistenza non è nota né al programmatore, né alla CPU;
• serve solo a velocizzare gli accessi a memoria.
Modulo 9 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
Perché dal 1982?
3.1 M112.00$ 9001993Pentium
1.2 M54.0020.00$ 3171989486
275 K11.405.00$ 911985386
134 K2.661.20$ 81982286
29 K0.750.33-19788086
n° transistorMIPS massimiMIPS inizialiCostoAnnoProcessore
Ogni 4 anni una nuova generazione.
Lo stesso processore raddoppia le proprie prestazioni:
⇒ miglioramento tecnologico (in orizzontale)
Tra una generazione e l'altra, triplica la complessità:
⇒ miglioramento architetturale (in verticale).
Come usiamo i transistori in più?
Per esempio per realizzare una memoria cachea bordo del processore, che lavora alla sua stessa frequenza di clock:
• cache L1 (di primo livello) - qualche KB.
La frequenza del processore, però, è cresciuta ancora, e la sua differenza rispetto alla DRAM si è enfatizzata:
• cache L2 (di secondo livello) esterna alprocessore - qualche centinaio di KB.
E se le cose degenerano...:• cache L3 (di terzo livello) esterna al
processore - qualche decina di MB!
Modulo 9 – U.D. 1 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 5
In sintesi...
Grazie alla località degli accessi a memoria da parte della CPU:
• possiamo copiare in una memoria ad alte prestazioni (cache) le celle richieste, che hanno maggiore probabilità di essere usate di nuovo;
• possiamo creare una gerarchia di cache via via più grandi e più lente man mano che ci allontaniamo dalla CPU e ci avviciniamo alla memoria di lavoro;
• le celle con più alta probabilità di riutilizzo sono ricopiate nella cache a bordo della CPU;
• tutte le celle disponibili sono presenti in memoria di lavoro.
Chiusura
Modulo 9 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Memoria cache epolitica Tag Associative
Architetture e reti logiche
Modulo 9 - Principali linee di evoluzione architetturale
Unità didattica 1 - Memoria cachee gerarchia di memoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Struttura generale
Abbiamo parlato di cache come contenitore di una copia dei blocchi di celle di memoria di lavoro che circondano la cella richiesta dalla CPU in un dato accesso a memoria.
Il progetto della cache richiede la seguente struttura generale:
• memoria di lavoro (MdL) divisa in blocchi di dimensione predefinita (es. 16 celle o parole);
• memoria cache (MC) divisa a sua volta in blocchi di dimensione uguale a quelli di MdL;
• ogni volta che non è presente una cella in cache, si trasporta in MC l'intero blocco di MdL che la contiene.
Modulo 9 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Problemi da risolvere
Mapping dei blocchi da MdL a MC:• ogni blocco di MdL in quale o quali blocchi di MC
può essere copiato.
Ricerca della parola richiesta dalla CPU:• HIT: la parola richiesta si trova in cache;• MISS: la parola richiesta NON si trova in cache e
deve essere prelevata da MdL.
Sostituzione del blocco di MC in caso di MISS:• quali azioni si devono intraprendere per
ottimizzare l'uso della cache.
Politica Tag Associative
127
:
:
1
0
MdLMCtag
Blocco 4095 B31G127
:
:
Blocco 256 B2G0
Blocco 255 B1G127
:
:
Blocco 129 B1G1
Blocco 128 B1G0
Blocco 127 B0G127Blocco × Gruppo 12731
::
::
Blocco 1 B0G1Blocco × Gruppo 10
Blocco 0 B0G0Blocco × Gruppo 0100000 0000000 0000
00000 0000000 111100000 0000001 0000
00000 0000001 1111
00000 1111111 1111
00000 1111111 0000
00001 0000000 0000
00001 0000000 111100001 0000001 0000
00001 0000001 1111
00001 1111111 0000
00001 1111111 111100010 0000000 0000
00010 0000000 1111
11111 1111111 0000
11111 1111111 1111
Modulo 9 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Mapping nella politica Tag Associative
Si definisce a priori una corrispondenza univoca fra:
• gruppo di blocchi in memoria di lavoro (MdL);• blocco di possibile destinazione in cache (MC).
Nell'esempio l'indirizzo generato dalla CPU(16 bit) ha la seguente struttura:
4 bit → 24=16 parole × blocco
7 bit → 27=128gruppi (blocchi di cache)
5 bit → 25=32 blocchi per gruppo
NP = N° parolanel blocco
NG = N° gruppodi blocchi
NB = N° blocconel gruppo
Ricerca parola in cache Tag Associative
tag [NG] = NB ?
HIT
CPU ↔ MC [NG & NP]
MISS
BloccoMdL [NB & NG] → BloccoMC [NG]NB → tag [NG]
CPU ↔ MC [NG & NP]
Address Bus: NB & NG & NP
noyes
Modulo 9 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
Caratteristiche Tag Associative
☺ Politica semplice:• il blocco richiesto dalla CPU può trovarsi solo in
un blocco di cache:⇒ la scoperta di HIT/MISS è rapida e priva di
problemi;• in caso di MISS, il blocco richiesto può essere
ricopiato in un'unica posizione.
L Politica non ottimizzata:• ogni blocco di MC ottimizza localmente
l'accessibilità ai blocchi di MdL cui è assegnato;• lo sfruttamento dei blocchi di MC non è
uniforme.
In sintesi...
Abbiamo individuato un metodo semplice di allocazione dei blocchi di MdL in MC.
La politica Tag Associative di allocazione dei blocchi di MdL in cache privilegia la semplicità realizzativa a scapito dello sfruttamento ottimale della MC.
Forse si può fare di meglio...
Modulo 9 – U.D. 1 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Chiusura
Modulo 9 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 1
Lezione – Politiche Fully Associative e Set Associative
Architetture e reti logiche
Modulo 9 - Principali linee di evoluzione architetturale
Unità didattica 1 - Memoria cachee gerarchia di memoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Problema
La politica Tag Associative è semplice da realizzare ma non ottimizza l'uso della memoria cache.
Il problema sta nell'allocazione fissa fra blocchi di MdL e blocco di MC.
Rimuoviamo l'ipotesi di allocazione fissa...
Modulo 9 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 2
Politica Fully Associative
127
:
:
1
0
MdLMCtag
Blocco 4095
:
:
:
Blocco i
:Blocco 127i
::
::
Blocco 1Blocco 11
Blocco 0Blocco 04095
Politica Fully Associative
Ogni blocco di MdL può andare a finire in qualsiasi blocco di MC.
Nell'esempio l'indirizzo generato dalla CPU(16 bit) ha la seguente struttura:
4 bit → 24=16 parole × blocco
12 bit → 212=4096blocchi in MdL
NP = N° parolanel blocco
NBMdL = N° bloccoin MdL
Modulo 9 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 3
Servono ulteriori elementi
Per poter verificare rapidamente se il blocco richiesto è in cache:
• memoria dei tag ad accesso associativo:– presentare il valore cercato;
– ottenere in un tempo di accesso l'indirizzo della cella che lo contiene (oppure segnalazione di assenza).
Per poter decidere dove scrivere il blocco cercato se non è presente:
• politica LRU (Least Recently Used);• un contatore a saturazione per ogni blocco di MC:
– azzerato quando si accede al blocco associato;
– incrementato di 1 se si accede a un altro blocco;
– almeno un contatore sempre saturo (11...11).
Memoria associativa
VCC
AR
Cell 0
Cell 1
Cell i
Modulo 9 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 4
Ricerca parola in cache Fully Associative
NBMC = ASS(NBMdL).tag
HIT
CPU ↔ MC [NBMC & NP]counters++
0 → counter [NBMC]
MISS
NBMC = ASS(11...11).counterBloccoMdL [NBMdL] → BloccoMC [NBMC]
NBMdL → tag [NBMC]CPU ↔ MC [NBMC & NP]
counters++0 → counter [NBMC]
Address Bus: NBMdL & NP
found not found
Caratteristiche Fully Associative
☺ Politica ottimizzata:• i blocchi presenti in MC sono sempre quelli che
nel recente passato sono stati più richiesti dalla CPU;
• abbiamo un ottimo globale, con sfruttamento omogeneo dei blocchi di MC.
L Politica complessa e costosa:• la ricerca del blocco richiesto implica il ricorso a
memoria associativa per i tag;• la ricerca del blocco di MC da sostituire implica
l'uso dei contatori a saturazione, che devono anch'essi essere accessibili in modo associativo.
Modulo 9 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 5
Politica Set Associative
Il solito compromesso:
• un blocco di MdL può essere copiato in un insieme limitato (set) di blocchi di MC;
• si parla di n-way cache Set Associative:n = 2 ogni blocco di MdL può essere copiato solo in 2
blocchi di MC;
n = 4 ogni blocco di MdL può essere copiato solo in 4 blocchi di MC;
n = 8 ogni blocco di MdL può essere copiato solo in 8 blocchi di MC;
Cerca di ottimizzare pregi e difetti dei due approcci precedenti.
In sintesi...
Abbiamo individuato metodi più sofisticati di allocazione dei blocchi di MdL in MC.
La politica Fully Associative di allocazione dei blocchi di MdL in cache privilegia lo sfruttamento ottimale della MC ma introduce pesanti complessità realizzative.
La politica Set Associative cerca il compromesso fra complessità e sfruttamento della cache.
Resta da discutere come gestire gli accessi in scrittura.
Modulo 9 – U.D. 1 – Lez. 3
Nello Scarabottolo – Architetture e reti logiche 6
Chiusura
Modulo 9 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 4 – Accesso in scrittura alla memoria cache
Architetture e reti logiche
Modulo 9 - Principali linee di evoluzione architetturale
Unità didattica 1 - Memoria cachee gerarchia di memoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Il problema della scrittura in cache
Se la CPU fa una scrittura in memoria:il dato in cache viene modificato rispetto al valore precedente.
• Politica store thru:– si modifica il dato sia in MC sia in MdL.
• Politica store in:– si modifica il dato soltanto in MC.
Cosa facciamo dell'originale in MdL?
Abbiamo due possibilità:
Modulo 9 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 2
Politica Store Thru
☺ Politica semplice:• le informazioni in MdL e le loro copie in cache
rimangono sempre congruenti;
• non si hanno ulteriori complessità a livello hardware.
L Politica non ottimizzata:• gli accessi a memoria in scrittura non vengono
velocizzati dalla presenza della cache;
• è accettabile solo perché gli accessi in scrittura sono decisamente meno di quelli in lettura:
– per produrre un risultato servono in genere più operandi;
– ma soprattutto, ci sono tutte le fasi di fetch!
Politica Store In
☺ Politica ottimizzata:• anche gli accessi in scrittura vengono velocizzati
se trovano la cella desiderata in cache.L Politica complessa:
• tra MC e MdL si crea incongruenza: la copia aggiornata è in cache;
• si potrebbe riscrivere il blocco da MC a MdLprima di eliminarlo, ma se i due blocchi sono uguali si perde tempo;
– si introduce un bit di modifica M (per ogni blocco di MC) che viene settato a ogni scrittura;
– se il blocco da sostituire ha M=1, lo si riscrive in MdL.
Modulo 9 – U.D. 1 – Lez. 4
Nello Scarabottolo – Architetture e reti logiche 3
In sintesi...
Due politiche di gestione delle scritture in memoria:
• Store Thru:– privilegia la facilità di realizzazione;
– non ottimizza l'uso della cache.
• Store In:– privilegia l'uso ottimizzato della cache;
– introduce complessità realizzative e gestionali per garantire la congruenza fra cache e Memoria di Lavoro.
Chiusura
Modulo 9 – U.D. 1 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 5 – Gerarchia di memoria
Architetture e reti logiche
Modulo 9 - Principali linee di evoluzione architetturale
Unità didattica 1 - Memoria cachee gerarchia di memoria
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Gerarchia di memoria
CPU
L1 cache
L2 cache
Memoria di Lavoro
Memoria di massa a disco
Memoria di backup ottica o a nastro
pochi registri GPR
qualche KB
qualche centinaio di KB
qualche centinaio di MB
qualche decina di GB
centinaia di GB a basso costo
Modulo 9 – U.D. 1 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 2
Rapporto fra gli ultimi due livelliMemoria di massa a disco magnetico:
• tempo di accesso: qualche msec.;• dimensioni: qualche decina di GB;• memoria di massa online:
– programmi di uso quotidiano;
– dati di uso quotidiano.
Memoria di massa a disco ottico o a nastro:• tempo di accesso: dalle centinaia di msec. alle
decine di sec.;• dimensioni: centinaia di GB a basso costo;• memoria di massa offline:
– originali dei programmi;
– backup dei propri dati.
Rapporto Memoria di Lavoro ÷ Disco
La memoria di lavoro (con i livelli di cachesoprastanti) è una memoria:
• di natura elettronica → tempi di lavoro in linea con quelli della CPU;
• ad accesso casuale → ogni cella richiesta èaccessibile nello stesso tempo (cachepermettendo...).
La memoria a disco magnetico è una memoria:• di natura meccanica → tempi di lavoro
inaccettabili per la CPU;• ad accesso sequenziale (o misto) → il tempo
di accesso varia a seconda della posizione del disco richiesta.
Modulo 9 – U.D. 1 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 3
Disk cache
Una parte della memoria di lavoro viene destinata a contenere i settori di disco più recentemente richiesti (come per la cache).
Si velocizza l'esecuzione di programmi che accedono spesso a file su disco.
Relativamente poco usata.
Memoria virtuale
Si fa vedere a ogni programma un intero spazio di indirizzamento, tutto a sua disposizione:
• la memoria virtuale (che sembra esserci, ma non c'è) vista da ogni programma viene parzialmentecaricata in memoria di lavoro da disco;
• quando la CPU esegue il programma, genera indirizzi virtuali;
• la quantità di memoria fisica presente non limita le dimensioni del singolo programma, solo le prestazioni.
• la quantità di memoria fisica presente non limita il numero di programmi in esecuzione, solo le prestazioni.
Modulo 9 – U.D. 1 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 4
Problemi da risolvere
Traduzione da indirizzo virtuale a indirizzo reale:
• dispositivo HW MMU: Memory Management Unit.Ricerca in memoria di lavoro della cella indirizzata.Gestione dei trasferimenti di blocchi di celle da disco a memoria di lavoro e viceversa:
• paginazione;• segmentazione;• segmentazione paginata.
Se ne riparla nell'insegnamento diSistemi Operativi.
Abbiamo inventato la memoria ideale!
Dischi ottici
Costoper bit
Tempo di accesso
Memorie a semiconduttore bipolari
Memorie a semiconduttore MOS
Dischi magnetici
Nastri
Memoria ideale
Modulo 9 – U.D. 1 – Lez. 5
Nello Scarabottolo – Architetture e reti logiche 5
In sintesi...
Uno sfruttamento oculato della località degli accessi ci dà una memoria:
• grande come un armadio di nastri;• veloce come la cache di livello 1 a bordo del
processore.
Tutto grazie a uno sforzo di progetto architetturale...
Riusciamo a fare qualcosa anche per la CPU ?...
Chiusura
Modulo 9 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 1 – Motivazioni del ricorso alle strutture pipeline
Architetture e reti logiche
Modulo 9 - Principali linee di evoluzione architetturale
Unità didattica 2 - Strutture pipeline
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Formulazione del problema
• La CPU passa la sua esistenza a eseguire istruzioni macchina;
• ogni istruzione macchina viene portata a termine in diverse fasi:
• Fetch;• Decode;• Exec;• Write Back;
• c'è poca sovrapposizione fra gli elementi coinvolti nelle varie fasi.
Adottiamo una catena di montaggio (pipeline)
Modulo 9 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 2
Funzionamento di una CPU normale
fase della Control Unit
tempo
Fetch
Decode
Exec
I0 I1
Write Back
F0
D0
E0
WB0
F1
D1
E1
WB1
Funzionamento di una CPU pipeline
Control Unit attive
ECU
DCU
FCU F0 F1
D0
F2
D1
E0
F3
D2
E1
F4
D3
E2
F5
D4
E3
I0 I1 I2 I3
tempo
I4
WB0 WB1 WB2 WB3 WB4
E4
D5
F6
E5
D6
F7
WBCU
Modulo 9 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 3
Efficacia della pipeline
Dopo il transitorio di avviamento, il tasso completamento istruzioni (ICR: Instruction Completion Rate) delle due CPU è:
ICRpipeline = NS × ICRnormal [MIPS]
dove NS = n° di Stadi (Number of Stages) della pipeline.
In realtà, le fasi non hanno tutte durata esattamente uguale:
ICRpipeline < NS × ICRnormal [MIPS]
La singola istruzione impiega circa lo stesso tempo.
Struttura di una CPU pipeline
IR
UnitControlDecode
MAR MDR
PC
ControlFetch
Unit
FCU
Control BusAddress Bus
Data Bus
ALU
SP
UnitControlExec
DCU ECU
Unit
Write BackControl
WBCU
GPR
Modulo 9 – U.D. 2 – Lez. 1
Nello Scarabottolo – Architetture e reti logiche 4
In sintesi...
• Una struttura a catena di montaggio (pipeline) consente di velocizzare l'esecuzione aumentando il numero di istruzioni macchina completate per unità di tempo [MIPS].
• L'incremento di prestazioni è dovuto a un intervento architetturale:– la tecnologia di realizzazione dell'integrato -
quindi la frequenza di lavoro - non cambia.
Vedremo quali sono i problemi nell'esecuzione di un programma reale.
Chiusura
Modulo 9 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 1
Lezione 2 – Problemi di esecuzionedi programmi con CPU pipeline
Architetture e reti logiche
Modulo 9 - Principali linee di evoluzione architetturale
Unità didattica 2 - Strutture pipeline
Nello Scarabottolo
Università degli Studi di Milano - Ssri - CDL ONLINE
Dipendenze (dependencies)
Durante l'esecuzione di programmi da parte di una CPU pipeline, si incontrano situazioni che comportano il rallentamento delle attività, quindi la perdita di efficacia.
• Control dependency:
il flusso di esecuzione delle istruzioni interrompe il normale comportamento sequenziale.
• Data dependency:due istruzioni vicine utilizzano uno stesso dato.
• Resource dependency:due istruzioni entrano in conflitto per una risorsa del sistema.
Modulo 9 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 2
Control dependency
Control Unit attive
WBCU
FCU F1F0
DCU
ECU
D0
F20F3F2
WB0
D1 D2
E0 E1
F23F22F21
tempo
D20 D21
E20
D22
E21
WB20
I0 I4
I0: BR I20
svuotamentodella pipeline
Branch prediction
I salti sono comunque una minoranza delle istruzioni (10% ÷ 20%).
I salti incondizionati possono essere risolti a livello di FCU.
Per migliorare l'efficienza con i salti condizionati, approccio statistico:
• se ho già incontrato l'istruzione di salto, mi comporto come la volta precedente;
• se NON ho mai incontrato l'istruzione di salto:– se è un salto all'indietro, provo a saltare (cicli);
– se è un salto in avanti, provo a NON saltare (costrutti if...then...else...).
Modulo 9 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 3
Branch Prediction Table (BPT)
• Quando FCU incontra istruzione di salto, consulta Branchaddress;
• se aveva già incontrato l'istruzione, si adegua a Statistics(Taken / Not taken) e eventualmente salta a Branchdestination;
• se non aveva incontrato l'istruzione, inserisce in BPT e salta indietro / NON salta in avanti;
• quando ECU risolve il salto, aggiorna BPT e in caso di scelta "sbagliata" di FCU provoca svuotamento della pipeline.
T200
StatisticsBranch destinationBranch address
Data dependency
WB0
I0
E3
D4
WB2
I1 I2
tempo
F6 F7
D5
E4
D6
E5
I3
WB4
I4
I0: ANDI1: ADD
R0,R0,#0R1,R1,R0
Control Unit attive
WBCU
DCU
FCU F0 F1 F2
ECU
D0 D1
E0
WB3
F4F3 F5
WB1
E2
D3
E1
D2
R0 azzerato da AND
R0 richiesto da ADD
Modulo 9 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 4
IR
UnitControlDecode
MAR MDR
PC
ControlFetch
Unit
FCU
Control BusAddress Bus
Data Bus
ALU
SP
UnitControlExec
DCU ECU
Unit
Write BackControl
WBCU
GPR
Data forwarding
ECU inoltra il dato dove richiesto (a se stessa)
R0,varR1,R1,#0
Control Unit attive
WBCU
DCU
I0: LDI1: AND
FCU F0 F1 F2
ECU
D0 D1
E0
WB3
F4F3 F5
WB1
E2
D3
E1
D2
WB0
I0
E3
D4
WB2
I1 I2
tempo
F6
D5
E4
I3
R1,R0,R0I2: ADD
Resource dependency
ECU accede a memoriaper leggere var
FCU accede a memoriaper fetch di I2
Modulo 9 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 5
Macchina di Harvard
DCUFCU
PC
MDRMAR
Unit
FetchControl
DecodeControl
Unit
IR
WBCUECU
GPR
ControlWrite Back
SP
ALU
ExecControl
Unit
Instructions Control Bus
Instructions Data BusInstructions Address Bus
Unit
MAR MDR
Variables Data BusVariables Address BusVariables Control Bus
Instructions cache
Variables cache
System Control BusSystem Address Bus
System Data Bus
CPU
Macchina di Harvard
La macchina di Harvard ha spazi di indirizzamento separati per istruzioni e dati variabili.
Con due cache a bordo della CPU elimino i conflitti fra fasi di fetch e fasi di accesso ai dati variabili, senza duplicare il System Bus.
Rimane il conflitto fra ECU e WBCU in caso di letture e scritture simultanee di dati variabili:
• si ricorre a tecniche di compilazione ottimizzata, che riordinano le istruzioni macchina in modo che una istruzione di STORE e una di LOAD non entrino in conflitto sull'accesso al Variables Bus.
Modulo 9 – U.D. 2 – Lez. 2
Nello Scarabottolo – Architetture e reti logiche 6
In sintesi...
I legami fra le istruzioni in esecuzione e i loro conflitti di accesso alle risorse possono provocare rallentamenti della pipeline dovuti a:
• control dependencies;• data dependencies;
• resource dependencies.
Si riesce a ridurre le inefficienze ricorrendo a soluzioni architetturali anche complesse:
• branch prediction;• data forwarding;• CPU con cache di primo livello separata per
istruzioni e variabili.
Chiusura
...e dell'insegnamento!