Architettura E Reti Logiche 7

Modulo 1 – U.D. 1 – Lez. 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 1 – U.D. 1 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 1 – U.D. 1 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 1 – U.D. 1 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 1 – U.D. 1 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 1 – U.D. 1 – Lez. 1

Prossimi passi

Dobbiamo decidere quali criteri adottare per rappresentare in modo elettrico informazioni.

Chiusura

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 1 – U.D. 1 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 1 – U.D. 1 – Lez. 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 Grandezza elettrica rappresentante (tensione o Voltaggio)

VMAX

0

Informazione da rappresentare (Temperatura)

Tmin

Nello Scarabottolo – Architetture e reti logiche

TMAX

2

Modulo 1 – U.D. 1 – Lez. 2

Rappresentazione analogica Grandezza elettrica rappresentante (tensione o Voltaggio)

VMAX

0

Informazione da rappresentare (Temperatura)

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 1 – U.D. 1 – Lez. 2

Rappresentazione analogica Grandezza elettrica rappresentante (tensione o Voltaggio)

VMAX

V0 0

Informazione da rappresentare (Temperatura)

Tmin

T0

TMAX

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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 1 – U.D. 1 – Lez. 2

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 Grandezza elettrica rappresentante (tensione o Voltaggio)

VMAX

V0 0

Informazione da rappresentare (Temperatura)

Tmin T0 T'0

Nello Scarabottolo – Architetture e reti logiche

TMAX

5

Modulo 1 – U.D. 1 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 1 – U.D. 1 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

7

Modulo 1– U.D. 1 – Lez. 3

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).

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 1– U.D. 1 – Lez. 3

Rappresentazione digitale Grandezza elettrica rappresentante (tensione o Voltaggio)

VMAX V2 V1 V0 0

Informazione da rappresentare (Temperatura)

Tmin

TMAX

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 1– U.D. 1 – Lez. 3

Rappresentato-rappresentante Grandezza elettrica rappresentante (tensione o Voltaggio)

VMAX

V0 0

Informazione da rappresentare (Temperatura)

Tmin Ti T0Tf

TMAX

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).

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 1– U.D. 1 – Lez. 3

Rappresentazione digitale: vantaggi Grandezza elettrica rappresentante (tensione o Voltaggio)

VMAX

V0 V'0 0

Informazione da rappresentare (Temperatura)

Tmin

T0

TMAX

Rappresentazione digitale: vantaggi È una rappresentazione che ben si presta a ELABORAZIONI ANCHE COMPLESSE:

• l'autocorrezione elimina gli errori di approssimazione.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 1– U.D. 1 – Lez. 3

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.

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 1– U.D. 1 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 1 – U.D. 1 – Lez. 4

Lezione 4 – Rappresentazione binaria 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. Particolarmente adatta a elaborazioni anche complesse.

Massimizzazione della robustezza: solo DUE valori del rappresentante, ciascuno associato a una CIFRA BINARIA (o BIT, dall'inglese BINARY DIGIT).

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 1 – U.D. 1 – Lez. 4

Rappresentazione binaria Grandezza elettrica rappresentante (tensione o Voltaggio)

VMAX

0

Informazione da rappresentare (Temperatura)

Tmin

Tsoglia

TMAX

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 1 – U.D. 1 – Lez. 4

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 1 – U.D. 1 – Lez. 4

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 1 – U.D. 2 – Lez. 1

Lezione 1 – Codifiche binarie dei 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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 1 – U.D. 2 – Lez. 1

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 x Unità didattica y Lezioni z1, z2, ...

Chiusura

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 1 – UD 3 – Lez. 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 Boole nel 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.

Nello Scarabottolo - Architetture e reti logiche

1

Modulo 1 – UD 3 – Lez. 1

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.

Nello Scarabottolo - Architetture e reti logiche

2

Modulo 1 – UD 3 – Lez. 1

Postulati P3, P4 e P5 (P3) 0 · 0 = 0

(P3') 1 + 1 = 1

(P4) 1 · 1 = 1

(P4') 0 + 0 = 0

(P5) 1 · 0 = 0 · 1 = 0

(P5') 0 + 1 = 1 + 0 = 1

Si sono definite le due operazioni di PRODOTTO LOGICO (AND) e di SOMMA LOGICA (OR).

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à.

Nello Scarabottolo - Architetture e reti logiche

3

Modulo 1 – UD 3 – Lez. 1

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

Nello Scarabottolo - Architetture e reti logiche

4

Modulo 1 – U.D. 3 – Lez. 2

Lezione 2 – Teoremi 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

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).

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 1 – U.D. 3 – Lez. 2

Teoremi a una variabile Identità (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

Involuzione (T4) (X) = X Complementi (T5)

X+X=1

(T5')

X·X=0

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

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 1 – U.D. 3 – Lez. 2

Teoremi a tre variabili

Associatività (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)] Nello Scarabottolo – Architetture e reti logiche

3

Modulo 1 – U.D. 3 – Lez. 2

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).

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 1 – U.D. 3 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 1 – U.D. 3 – Lez. 3

Lezione 3 – Aritmetica con l'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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 1 – U.D. 3 – Lez. 3

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:

A

B

S

R

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 1 – U.D. 3 – Lez. 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 R

HA S

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 1 – U.D. 3 – Lez. 3

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 B1 tenendo conto anche dell'eventuale riporto R0 per 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: A1

B1

R0

S1

R1

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 1 – U.D. 3 – Lez. 3

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

A1 B1 R1

FA

R0

S1 Nello Scarabottolo – Architetture e reti logiche

5

Modulo 1 – U.D. 3 – Lez. 3

Circuito per la somma a 2 bit

R1

A1 B1

A0 B0

FA

HA

S1

R0

S0

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.

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 1 – U.D. 3 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

7

Modulo 1 – U.D. 3 – Lez. 4

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 1 – U.D. 3 – Lez. 4

Negatore bipolare

CC

RU U C

I RI

B

E

Porta NOT

OUT OUT Nello Scarabottolo – Architetture e reti logiche

2

Modulo 1 – U.D. 3 – Lez. 4

Porta AND

OUT

Porta OR

OUT

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 1 – U.D. 3 – Lez. 4

Porta NAND

OUT

Porta NOR

OUT

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 1 – U.D. 3 – Lez. 4

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 2 – U.D. 1 – Lez. 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 f x y z

Descrizione strutturale

Nello Scarabottolo – Architettura e reti logiche

1

Modulo 2 – U.D. 1 – Lez. 1

Esempio di rete combinatoria w f x y z

Descrizione comportamentale

Tabella delle verità #

w

x

y

z

f

0

0

0

0

0

0

1

0

0

0

1

1

2

0

0

1

0

0

3

0

0

1

1

0

4

0

1

0

0

0

5

0

1

0

1

1

6

0

1

1

0

0

7

0

1

1

1

0

8

1

0

0

0

0

9

1

0

0

1

1

10

1

0

1

0

0

11

1

0

1

1

0

12

1

1

0

0

0

13

1

1

0

1

1

14

1

1

1

0

1

15

1

1

1

1

1

Nello Scarabottolo – Architettura e reti logiche

2

Modulo 2 – U.D. 1 – Lez. 1

In sintesi... Analisi della rete combinatoria: • dalla struttura, • al comportamento. Interessa passare: • dal comportamento, • alla struttura. Dobbiamo trovare strumenti che ci consentano di effettuare una sintesi.

Chiusura

Nello Scarabottolo – Architettura e reti logiche

3

Modulo 2 – U.D. 1 – Lez. 2

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.

Nello Scarabottolo – Architettura e reti logiche

1

Modulo 2 – U.D. 1 – Lez. 2

Prima tabella delle verità #

w

x

y

z

f

0

0

0

0

0

0

1

0

0

0

1

0

2

0

0

1

0

0

3

0

0

1

1

0

4

0

1

0

0

0

5

0

1

0

1

0

6

0

1

1

0

0

7

0

1

1

1

0

8

1

0

0

0

0

9

1

0

0

1

0

10

1

0

1

0

0

11

1

0

1

1

1

12

1

1

0

0

0

13

1

1

0

1

0

14

1

1

1

0

0

15

1

1

1

1

0

Sintesi della prima rete

Nello Scarabottolo – Architettura e reti logiche

2

Modulo 2 – U.D. 1 – Lez. 2

Seconda tabella delle verità #

w

x

y

z

f

0

0

0

0

0

0

1

0

0

0

1

0

2

0

0

1

0

0

3

0

0

1

1

0

4

0

1

0

0

0

5

0

1

0

1

0

6

0

1

1

0

1

7

0

1

1

1

0

8

1

0

0

0

0

9

1

0

0

1

0

10

1

0

1

0

0

11

1

0

1

1

1

12

1

1

0

0

0

13

1

1

0

1

0

14

1

1

1

0

0

15

1

1

1

1

0

Sintesi della seconda rete

Nello Scarabottolo – Architettura e reti logiche

3

Modulo 2 – U.D. 1 – Lez. 2

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.

Nello Scarabottolo – Architettura e reti logiche

4

Modulo 2 – U.D. 1 – Lez. 2

Chiusura

Nello Scarabottolo – Architettura e reti logiche

5

Modulo 2 – U.D. 1 – Lez. 3

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à #

w

x

y

z

f

0

0

0

0

0

1

1

0

0

0

1

1

2

0

0

1

0

0

3

0

0

1

1

1

4

0

1

0

0

1

5

0

1

0

1

1

6

0

1

1

0

1

7

0

1

1

1

1

8

1

0

0

0

1

9

1

0

0

1

1

10

1

0

1

0

1

11

1

0

1

1

1

12

1

1

0

0

1

13

1

1

0

1

1

14

1

1

1

0

1

15

1

1

1

1

1

Nello Scarabottolo – Architettura e reti logiche

1

Modulo 2 – U.D. 1 – Lez. 3

Sintesi della prima rete

Seconda tabella delle verità #

w

x

y

z

f

0

0

0

0

0

1

1

0

0

0

1

1

2

0

0

1

0

0

3

0

0

1

1

1

4

0

1

0

0

1

5

0

1

0

1

1

6

0

1

1

0

1

7

0

1

1

1

1

8

1

0

0

0

0

9

1

0

0

1

1

10

1

0

1

0

1

11

1

0

1

1

1

12

1

1

0

0

1

13

1

1

0

1

1

14

1

1

1

0

1

15

1

1

1

1

1

Nello Scarabottolo – Architettura e reti logiche

2

Modulo 2 – U.D. 1 – Lez. 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.

Nello Scarabottolo – Architettura e reti logiche

3

Modulo 2 – U.D. 1 – Lez. 3

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

Nello Scarabottolo – Architettura e reti logiche

4

Modulo 2 – U.D. 1 – Lez. 4

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à.

Nello Scarabottolo – Architettura e reti logiche

1

Modulo 2 – U.D. 1 – Lez. 4

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:

xLyGzI

Primo esempio w f x y z

Nello Scarabottolo – Architettura e reti logiche

2

Modulo 2 – U.D. 1 – Lez. 4

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).

Nello Scarabottolo – Architettura e reti logiche

3

Modulo 2 – U.D. 1 – Lez. 4

Chiusura

Nello Scarabottolo – Architettura e reti logiche

4

Modulo 2 – U.D. 2 – Lez. 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 2 – U.D. 2 – Lez. 1

Tabella delle verità #

w

x

y

z

f

0

0

0

0

0

0

1

0

0

0

1

1

2

0

0

1

0

0

3

0

0

1

1

0

4

0

1

0

0

0

5

0

1

0

1

1

6

0

1

1

0

0

7

0

1

1

1

0

8

1

0

0

0

0

9

1

0

0

1

1

10

1

0

1

0

0

11

1

0

1

1

0

12

1

1

0

0

0

13

1

1

0

1

1

14

1

1

1

0

1

15

1

1

1

1

1

• 6 uni • 10 zeri

Altre possibili notazioni

∑ (1,5,9,13,14,15) 1

Indica le posizioni degli UNI della funzione, e suggerisce la sintesi come Somma di Prodotti (da cui il simbolo di Sommatoria)

∏ (0,2,3,4,6,7,8,10,11,12) 0

Indica le posizioni degli ZERI della funzione, e suggerisce la sintesi come Prodotto di Somme (da cui il simbolo di Produttoria)

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 2 – U.D. 2 – Lez. 1

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).

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 2 – U.D. 2 – Lez. 1

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 mintermini otteniamo 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. Nello Scarabottolo – Architetture e reti logiche

4

Modulo 2 – U.D. 2 – Lez. 1

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 maxtermini otteniamo 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. Nello Scarabottolo – Architetture e reti logiche

5

Modulo 2 – U.D. 2 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 2 – U.D. 2 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 2 – U.D. 2 – Lez. 2

Rappresentazione geometrica dei numeri binari: gli n-cubi 0- cubo 0

1

00

01

1100

1101

1- cubo 1000

1001

2- cubo

0100 0000 10

4- cubo

0001

11 100

000

1110

101 001

0110 0010

3- cubo 1010 110 010

0101

0111

1111

0011 1011

111 011

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).

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 2 – U.D. 2 – Lez. 2

Uso dell'n-cubo

1100

1101

• Nella funzione di esempio, esistono 6 implicanti di ordine 1 (associati a 1-cubi, cioè a segmenti).

1001

1000

0100 0000

0101

0001

1110 0110 0010 1010

0111 0011 1011

• Ogni p-sottocubo associato a UNI della funzione indica un possibile implicante.

1111

• Nella funzione di esempio, esiste 1 implicante di ordine 2 (associato a un 2-cubo, cioè a un quadrato).

Tipi di implicanti Il 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 un p-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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 2 – U.D. 2 – Lez. 2

Tipi di implicanti

1100

1101

1001

1000

0100 0000

0101

0001

1110 0110 0010 1010

0111

1111

0011 1011

Tipi di implicati Il 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 un p-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. Nello Scarabottolo – Architetture e reti logiche

4

Modulo 2 – U.D. 2 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 2 – U.D. 2 – Lez. 3

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 2 – U.D. 2 – Lez. 3

Mappe di Karnaugh

z y

0

1

0

0

1

1

2

3

yz wx

2-cubo

00 01

yz x

11

00

01

11

10

0

0

1

3

2

1

4

5

7

6

10

00

01

11

10

0

1

3

2

4

5

7

6

12

13

15

14

8

9

11

10

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 2 – U.D. 2 – Lez. 3

Uso delle mappe di Karnaugh yz x

00 01 11 10 0

0

1

1

0

1

0

1

0

0

yz x

00 01 11 10 0

1

1

0

1

1

1

0

0

1

Uso delle mappe di Karnaugh yz wx 00 01 11 10 00

1

0

1

0

01

1

1

1

0

11

1

1

1

0

10

1

0

0

0

yz wx 00 01 11 10 00

1

0

0

1

01

1

1

0

0

11

0

0

1

0

10

1

0

0

1

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 2 – U.D. 2 – Lez. 3

Mappe di Karnaugh a 5 variabili yz

yz

v=0

wx 00 01 11 10

wx 00 01 11 10

00

0

0

0

0

00

0

0

0

0

01

0

1

0

0

01

0

1

0

0

11

0

1

0

0

11

0

1

0

1

10

0

0

0

0

10

0

0

0

1

v=1

Mappe di Karnaugh a 6 variabili yz

uv = 00

yz

wx 00 01 11 10

wx 00 01 11 10

00

0

0

1

1

00

0

0

1

1

01

0

1

0

0

01

0

1

0

0

11

0

1

0

0

11

0

1

0

1

10

0

0

0

0

10

0

0

0

1

yz

uv = 10

uv = 01

yz

wx 00 01 11 10

wx 00 01 11 10

00

0

0

0

0

00

0

0

0

0

01

0

1

0

0

01

0

1

0

0

11

0

1

0

0

11

0

1

0

1

10

0

0

0

0

10

0

0

0

1

Nello Scarabottolo – Architetture e reti logiche

uv = 11

4

Modulo 2 – U.D. 2 – Lez. 3

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 Quine McCluskey) non fondamentali per il nostro insegnamento.

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 2 – U.D. 2 – Lez. 4

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 trascodificatore da BCD a 7-segmenti.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 2 – U.D. 2 – Lez. 4

Tabella delle verità del trascodificatore #

w

x

y

z

a

b

c

d

e

f

g

0

0

0

0

0

1

1

1

1

1

1

0

1

0

0

0

1

0

1

1

0

0

0

0

2

0

0

1

0

1

1

0

1

1

0

1

3

0

0

1

1

1

1

1

1

0

0

1

4

0

1

0

0

0

1

1

0

0

1

1

5

0

1

0

1

1

0

1

1

0

1

1

6

0

1

1

0

1

0

1

1

1

1

1

7

0

1

1

1

1

1

1

0

0

0

0

8

1

0

0

0

1

1

1

1

1

1

1

9

1

0

0

1

1

1

1

0

0

1

1

10

1

0

1

0

×

×

×

×

×

×

×

11

1

0

1

1

×

×

×

×

×

×

×

12

1

1

0

0

×

×

×

×

×

×

×

13

1

1

0

1

×

×

×

×

×

×

×

14

1

1

1

0

×

×

×

×

×

×

×

15

1

1

1

1

×

×

×

×

×

×

×

Mappa di Karnaugh del segmento a f (w,x,y,z) =

∑ (0,2,3,5,6,7,8,9) + 1

Sintesi SP

∑ (10,11,12,13,14,15) ×

yz wx

00

01

11

10

00

1

0

1

1

01

0

1

1

1

11

×

×

×

×

10

1

1

×

×

Sintesi PS

Sono reti diverse! Nello Scarabottolo – Architetture e reti logiche

2

Modulo 2 – U.D. 2 – Lez. 4

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

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 2 – U.D. 2 – Lez. 5

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-segmenti 4 ingressi: w, x, y, z 7 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?

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 2 – U.D. 2 – Lez. 5

Primo esempio f1(x,y,z) =

∑ (1,3,7)

f2(x,y,z) =

1

f1

yz

x 00

1

f2 01

11

10

∑ (3,6,7)

yz

x 00

01

11

10

0

0

1

1

0

0

0

0

1

0

1

0

0

1

0

1

0

0

1

1

Realizzazione ottimizzata

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 2 – U.D. 2 – Lez. 5

Secondo esempio f1(x,y,z) =

∑ (1,3,7)

f2(x,y,z) =

1

f1

yz

x 00

1

f2 01

11

10

∑ (2,6,7)

yz

x 00

01

11

10

0

0

1

1

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

Realizzazione ottimizzata

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 2 – U.D. 2 – Lez. 5

Implicante primo di più uscite L'implicante xyz è un implicante primo della funzione f1 ⋅ f2 Si evidenzia nella mappa di Karnaugh della funzione prodotto: f1 ⋅f2

yz

x 00 01 11 10 0

0

0

0

0

1

0

0

1

0

Nel caso di sintesi PS, servirebbe la mappa di Karnaugh della funzione f1 + 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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 2 – U.D. 2 – Lez. 5

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 2 – U.D. 3 – Lez. 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).

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 2 – U.D. 3 – Lez. 1

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 passare direttamente da 0 a 1). – Alea dinamica discendente (l'uscita dovrebbe passare direttamente da 1 a 0).

Esempio di alea statica di tipo 1 Espressione logica

yz x

00 01 11 10 0

0

1

1

1

1

0

0

0

1

Schema circuitale

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 2 – U.D. 3 – Lez. 1

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:

f 10 yz 10 xz 10 z 10 y 10 x 10 tempo

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 2 – U.D. 3 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 2 – U.D. 3 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 2 – U.D. 3 – Lez. 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:

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 2 – U.D. 3 – Lez. 2

Mappa di Karnaugh Riportiamo gli implicanti sulla mappa: yz

wx

00

01

11

10

00 01 11 10

Abbiamo identificato le alee statiche di tipo 1.

Mappa di Karnaugh Consideriamo il termine spurio: yz

wx

00

01

11

10

00

0

0

0

0

01

0

0

1

1

11

0

0

1

0

10

0

0

1

0

Abbiamo identificato le alee statiche di tipo 0 e le alee dinamiche. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 2 – U.D. 3 – Lez. 2

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 yz x

00 01 11 10 0

0

1

1

1

1

0

0

0

1

yz wx

00 01 11 10

00

1

0

0

1

01

1

1

0

0

11

1

1

0

0

10

1

0

0

1

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 2 – U.D. 3 – Lez. 2

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)

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 2 – U.D. 3 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 3 – U.D. 1 – Lez. 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

Nello Scarabottolo – Architetture e reti logiche

y

y

1

Modulo 3 – U.D. 1 – Lez. 1

Diagramma temporale

S R y y

1 0 1 0 1 0 1 0 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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 1 – Lez. 1

Tabella di eccitazione del bistabile SR

y

Y

S

R

0

0

0

×

0

1

1

0

1

0

0

1

1

1

×

0

Schema elettrico del bistabile SR

S

y

R

y

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 1 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 3 – U.D. 1 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 1 – Lez. 2

Schema elettrico del bistabile SRC

S

y

C R

y

Bistabile D Bistabile Data con segnale di Controllo: • capace di memorizzare un dato da un bit.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 1 – Lez. 2

Tabella di eccitazione del bistabile D y

Y

D

0

0

0

0

1

1

1

0

0

1

1

1

Stato prossimo ed eccitazione coincidono.

Schema elettrico del bistabile D

D

y

C y

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 1 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 3 – U.D. 1 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 3 – U.D. 1 – Lez. 3

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.

Nello Scarabottolo - Architetture e reti logiche

1

Modulo 3 – U.D. 1 – Lez. 3

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 staticizzati dal Master vengono propagati dallo Slave. Chiamiamo questi bistabili FLIP-FLOP.

Schema elettrico del flip-flop SR

S

y

C R

Nello Scarabottolo - Architetture e reti logiche

y

2

Modulo 3 – U.D. 1 – Lez. 3

Schema elettrico del flip flop D

D

y

C y

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.

Nello Scarabottolo - Architetture e reti logiche

3

Modulo 3 – U.D. 1 – Lez. 3

Tabella di eccitazione del flip-flop JK

y

Y

J

K

0

0

0

×

0

1

1

×

1

0

×

1

1

1

×

0

Schema elettrico del flip-flop JK

J

y

C K

Nello Scarabottolo - Architetture e reti logiche

y

4

Modulo 3 – U.D. 1 – Lez. 3

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

y

Y

T

0

0

0

0

1

1

1

0

1

1

1

0

Nello Scarabottolo - Architetture e reti logiche

5

Modulo 3 – U.D. 1 – Lez. 3

Schema elettrico del flip-flop T

y T y

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.

Nello Scarabottolo - Architetture e reti logiche

6

Modulo 3 – U.D. 1 – Lez. 3

Chiusura

Nello Scarabottolo - Architetture e reti logiche

7

Modulo 3 – U.D. 2 – Lez. 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 x1 x1 x2

S

x1 x2

R

x1 x2

S

x1 x2

R

y1

z1

y1 y2

x2

z2 y2

Evidenziamo i legami combinatori fra ingressi alla rete, uscite dei bistabili e uscite della rete (vedi dispensa). Nello Scarabottolo - Architetture e reti logiche

1

Modulo 3 – U.D. 2 – Lez. 1

Tabella di z in funzione di x e y #

x1

x2

y1

y2

z1

z2

0

0

0

0

0

#s

0

1

1

0

0

0

1

1

0

2

0

0

1

0

0

1

1

3

0

0

1

1

1

1

1

4

0

1

0

0

0

0

5

0

1

0

1

1

0

6

0

1

1

0

1

1

7

0

1

1

1

6

1

0

9

0

1

0

0

0

1

1

1

4

8

1

0

0

0

9

1

0

0

1

10

1

0

1

0

11

1

0

1

1

12

1

1

0

0

14

0

0

13

1

1

0

1

15

0

0

14

1

1

1

0

0

1

15

1

1

1

1

1

0

11

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).

Nello Scarabottolo - Architetture e reti logiche

2

Modulo 3 – U.D. 2 – Lez. 1

Stato PRESENTE e stato PROSSIMO #

x1

x2

y1

y2

Y1

Y2

z1

z2

0

0

0

0

0

0

0

0

1

1

0

0

0

1

0

1

1

0

2

0

0

1

0

0

0

1

1

3

0

0

1

1

0

1

1

1

4

0

1

0

0

0

0

0

0

5

0

1

0

1

0

0

1

0

6

0

1

1

0

1

0

1

1

7

0

1

1

1

1

0

1

0

8

1

0

0

0

0

1

0

1

9

1

0

0

1

0

1

0

0

10

1

0

1

0

1

1

0

1

11

1

0

1

1

1

1

1

1

12

1

1

0

0

1

0

0

0

13

1

1

0

1

1

1

0

0

14

1

1

1

0

1

0

0

1

15

1

1

1

1

1

1

1

0

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... Nello Scarabottolo - Architetture e reti logiche

3

Modulo 3 – U.D. 2 – Lez. 1

Chiusura

Nello Scarabottolo - Architetture e reti logiche

4

Modulo 3 – U.D. 2 – Lez. 2

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. Nello Scarabottolo - Architetture e reti logiche

1

Modulo 3 – U.D. 2 – Lez. 2

Tabella delle uscite Come indicato nella dispensa, fornisce le uscite z come funzione dello stato presente y e degli ingressi x: z1 z2

x1 x2

y1y2

00

01

11

10

00

01

00

00

01

01

10

10

00

00

11

11

10

10

11

10

11

11

01

01

Il legame è combinatorio: già noto!

Tabella delle transizioni Come indicato nella dispensa, fornisce lo stato prossimo Y come funzione dello stato presente y e degli ingressi x: Y1Y2

x1 x2

y1y2

00

01

11

10

00

00

00

10

01

01

01

00

11

01

11

01

10

11

11

10

00

10

10

11

Nello Scarabottolo - Architetture e reti logiche

2

Modulo 3 – U.D. 2 – Lez. 2

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 y provocando 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: S1R1,S2R2 y1y2

x1 x2 00

01

11

10

00

01,00

00,01

10,00

00,10

01

01,00

00,01

10,00

00,10

11

01,00

00,01

10,00

00,10

10

01,00

00,01

10,00

00,10

Nello Scarabottolo - Architetture e reti logiche

3

Modulo 3 – U.D. 2 – Lez. 2

Transizioni e eccitazioni Come illustrato nella dispensa, sono legate dalla tabella delle eccitazioni del bistabile usato: y

Y

S

R

0

0

0

×

0

1

1

0

1

0

0

1

1

1

×

0

Le eccitazioni della rete sono gli ingressi ai bistabili necessari per far evolvere lo stato presente y verso l'opportuno stato prossimo Y.

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. Nello Scarabottolo - Architetture e reti logiche

4

Modulo 3 – U.D. 2 – Lez. 2

Chiusura

Nello Scarabottolo - Architetture e reti logiche

5

Modulo 3 – U.D. 2 – Lez. 3

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 y provocando movimenti del punto di lavoro in verticale.

Nello Scarabottolo - Architetture e reti logiche

1

Modulo 3 – U.D. 2 – Lez. 3

Tabella degli stati Della tabella delle transizioni, si può dare una rappresentazione simbolica, che trascuri le codifiche binarie degli stati: S

x1 x2 s

00

01

11

10

a

a

a

d

b

b

b

a

c

b

c

b

d

c

c

d

a

d

d

c

La tabella riporta lo stato prossimo S in funzione dello stato presente s e degli ingressi x.

Diagramma degli stati

Nello Scarabottolo - Architetture e reti logiche

2

Modulo 3 – U.D. 2 – Lez. 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

Nello Scarabottolo - Architetture e reti logiche

3

Modulo 3 – U.D. 3 – Lez. 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. Nello Scarabottolo - Architetture e reti logiche

1

Modulo 3 – U.D. 3 – Lez. 1

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).

Nello Scarabottolo - Architetture e reti logiche

2

Modulo 3 – U.D. 3 – Lez. 1

Diagramma degli stati alla Mealy

Macchine alla Moore

Nello Scarabottolo - Architetture e reti logiche

3

Modulo 3 – U.D. 3 – Lez. 1

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) del diagramma degli stati.

Diagramma degli stati alla Moore

Nello Scarabottolo - Architetture e reti logiche

4

Modulo 3 – U.D. 3 – Lez. 1

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

Nello Scarabottolo - Architetture e reti logiche

5

Modulo 3 – U.D. 3 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 3 – Lez. 2

Tabella degli stati

S,z

x s

0

1

a b c d

Tabelle delle transizioni e delle uscite S,z

Y1Y2 y1y2

x s

0

1

a

a,0

b,0

b

c,0

b,0

c

a,0

d,1

d

a,0

b,0

x

Scegliamo arbitrariamente 4 codifiche binarie per i 4 stati della tabella degli stati: z

0

1

x

y1y2

00

00

01

01

11

11

10

10

Nello Scarabottolo – Architetture e reti logiche

0

1

2

Modulo 3 – U.D. 3 – Lez. 2

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 bistabile per costruire la tabella di eccitazione della rete; • scegliamo il flip-flop SR.

Y1Y2 y1y2

Tabella delle eccitazioni

x 0

1

00

00

01

01

11

01

11

00

10

10

00

01

y

Y

S

R

0

0

0

×

0

1

1

0

1

0

0

1

1

1

×

0

S1R1,S2R2 x y1y2

0

1

00 01 11 10

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 3 – Lez. 2

Sintesi della rete La tabella delle eccitazioni consente la sintesi combinatoria delle 4 funzioni: S1 = R1 = S2 = R2 =

f f f f

(x, y1, (x, y1, (x, y1, (x, y1,

y2) y2) y2) 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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 3 – U.D. 3 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 3 – U.D. 3 – Lez. 3

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 3 – Lez. 3

Tabella degli stati

S

x s

0

1

z

a b c d

Tabelle delle transizioni e delle uscite S

x s

0

1

z

a

a

b

0

b

c

b

0

c

a

d

0

d

a

b

1

Y1Y2 y1y2

Scegliamo arbitrariamente 4 codifiche binarie per i 4 stati della tabella degli stati:

x 0

1

y1y2

00

00

01

01

11

11

10

10

Nello Scarabottolo – Architetture e reti logiche

z

2

Modulo 3 – U.D. 3 – Lez. 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 bistabile per costruire la tabella di eccitazione della rete. • scegliamo il flip-flop JK.

Y1Y2 y1y2

Tabella delle eccitazioni

x 0

1

00

00

01

y

Y

J

K

01

11

01

0

0

0

×

11

00

10

0

1

1

×

10

00

01

1

0

×

1

1

1

×

0

J1K1,J2K2

x

y1y2

0

1

00 01 11 10

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 3 – Lez. 3

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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 3 – U.D. 3 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 3 – U.D. 3 – Lez. 4

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...).

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 3 – Lez. 4

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)

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 3 – Lez. 4

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)

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 3 – Lez. 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

0

d

0

0 a/00

1

b/00

0

c/00

0 1

d/10

1

e/10

1 1

i/01

a

0 1

a

k/10

0 0

1

1

j/10

0

a

f/10

1

g/00

h/00

0

1

d

0 1

b

Nello Scarabottolo – Architetture e reti logiche

d

0

l/11

1

e

4

Modulo 3 – U.D. 3 – Lez. 4

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 3 – U.D. 4 – Lez. 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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 4 – Lez. 1

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à).

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 4 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 4 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 4 – Lez. 2

Tabella degli stati corrispondente

S,z

x s

0

1

a

b,0

a,0

b

d,0

c,0

c

e,1

a,0

d

d,0

f,0

e

b,0

a,0

f

g,1

a,0

g

b,0

a,0

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 4 – Lez. 2

Tabella delle indistinguibilità b S,z

x

s

0

1

a b,0

a,0

b d,0

c,0

c e,1

a,0

d d,0

f,0

e b,0

a,0

f g,1

a,0

g b,0

a,0

c d e f g a

b

c

d

e

f

Grafo delle indistinguibilità Nodi: gli stati. Archi: le indistinguibilità (eventualmente condizionate). Scopo: individuare gruppi di stati tra loro indistinguibili.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 4 – Lez. 2

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

S,z

x s

0

1

a

b,0

a,0

b

d,0

c,0

c

e,1

a,0

d

d,0

f,0

s

e

b,0

a,0

α

f

g,1

a,0

β

g

b,0

a,0

γ

Nello Scarabottolo – Architetture e reti logiche

S,z

x 0

1

4

Modulo 3 – U.D. 4 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 3 – U.D. 5 – Lez. 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).

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 5 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 5 – Lez. 1

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 (nodi del 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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 5 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 3 – U.D. 5 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 5 – Lez. 2

Tabella degli stati

S,z

IN s

A

B

a b c d

Tabella e grafo delle indistinguibilità S,z

IN s

A

B

a

b,0

a,0

b

b

b,0

c,0

c

c

b,0

d,1

d

d

b,0

a,0

a

S,z

b

c

IN s

A

B

α

Tabella degli stati ridotta: Nello Scarabottolo – Architetture e reti logiche

b c

2

Modulo 3 – U.D. 5 – Lez. 2

Tabelle delle transizioni e delle uscite S,z

IN s

A

B

α

b,0

α,0

b

b,0

c,0

c

b,0

α,1

Y1Y2 y1y2

Scegliamo arbitrariamente 3 codifiche binarie per i 3 stati della tabella degli stati:

IN

z A

B

IN

y1y2

00

00

01

01

11

11

A

B

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 zB a seconda di quale dei due ingressi ha generato l'impulso: in questo modo è funzione anche degli ingressi, come normale in una macchina alla Mealy. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 5 – Lez. 2

Rete di generazione dell'uscita z

Tabella delle eccitazioni Y1Y2

IN

y1y2

A

B

00

01

00

01

01

11

0

0

0

×

0

1

1

0

11

01

00

1

0

0

1

1

1

×

0

S1R1,S2R2

y

Y

S

R

IN

y1y2

A

B

00 01 11

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 3 – U.D. 5 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 3 – U.D. 5 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 3 – U.D. 5 – Lez. 3

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 5 – Lez. 3

Tabella degli stati

S

IN s

A

B

z

a b c d

Tabella e grafo delle indistinguibilità

S

IN s

A

B

z

a

a

b

0

b

b

a

c

0

c

c

d

c

0

d

d

a

b

1

a

b

c

La tabella degli stati è già minima.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 5 – Lez. 3

Tabelle delle transizioni e delle uscite S

Y1Y2 y1y2

IN s

A

B

z

a

a

b

0

b

a

c

0

c

d

c

0

d

a

b

1

Scegliamo arbitrariamente 4 codifiche binarie per i 4 stati della tabella degli stati:

IN

z A

B

y1y2

00

00

01

01

11

11

10

10

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 5 – Lez. 3

Tabella delle eccitazioni Y1Y2

IN

y1y2

A

B

00

00

01

01

00

11

11

10

10

00

y

Y

J

K

0

0

0

×

0

1

1

×

11

1

0

×

1

01

1

1

×

0

J1K1,J2K2 y1y2

IN A

B

00 01 11 10

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. Nello Scarabottolo – Architetture e reti logiche

4

Modulo 3 – U.D. 5 – Lez. 3

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. Nello Scarabottolo – Architetture e reti logiche

5

Modulo 3 – U.D. 5 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 3 – U.D. 5 – Lez. 4

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.

Nello Scarabottolo – Architettura e reti logiche

1

Modulo 3 – U.D. 5 – Lez. 4

Diagramma e tabella degli stati

S

IN s

A

B

C

z

a b c d e f

Tabella e grafo delle indistinguibilità S

IN s

A

B

C

z

a

d

b

c

0

b

a

e

c

0

c

a

b

f

0

d

a

e

f

1

e

d

b

f

1

f

d

e

c

1

b c d e f a

b

c

d

e

La tabella degli stati è già minima.

Nello Scarabottolo – Architettura e reti logiche

2

Modulo 3 – U.D. 5 – Lez. 4

Tabelle delle transizioni e delle uscite S

IN s

A

B

C

z

a

d

b

c

0

b

a

e

c

0

c

a

b

f

0

d

a

e

f

1

e

d

b

f

1

f

d

e

c

1

Y1Y2Y3

Scegliamo arbitrariamente 6 codifiche binarie per i 6 stati della tabella degli stati: z

IN

y1y2y3

A

y1y2y3

C

B

000

000

001

001

010

010

011

011

100

100

101

101

Y1Y2Y3 y1y2y3

Tabella delle eccitazioni

IN A

B

C

000

011

001

010

001

000

100

010

010

000

001

101

0

0

0

×

1

1

0

y

Y

S

R

011

000

100

101

0

100

011

001

101

1

0

0

1

101

011

100

010

1

1

×

0

S1R1,S2R2,S3R3 y1y2

IN A

B

C

000 001 010 011 100 101

Nello Scarabottolo – Architettura e reti logiche

3

Modulo 3 – U.D. 5 – Lez. 4

Chiusura

Nello Scarabottolo – Architettura e reti logiche

4

Modulo 3 – U.D. 5 – Lez. 5

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 z genera 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.

Nello Scarabottolo – Architettura e reti logiche

1

Modulo 3 – U.D. 5 – Lez. 5

Diagramma e tabella degli stati

S,z

IN s

A

B

C

a b c d e f

Tabella e grafo delle indistinguibilità S,z

IN

b

s

A

B

C

a

a,0

b,0

a,0

c

b

a,0

b,0

c,0

d

c

a,0

d,0

a,0

d

a,0

b,0

e,0

e

f,1

e,0

e,0

f

a,0

b,0

a,0

e f a S,z

b

c

d

e

IN s

A

B

C

α b c

Tabella degli stati ridotta: Nello Scarabottolo – Architettura e reti logiche

d e

2

Modulo 3 – U.D. 5 – Lez. 5

Tabelle delle transizioni e delle uscite S,z

IN s

A

B

C

α

α,0

b,0

α,0

b

α,0

b,0

c,0

c

α,0

d,0

α,0

d

α,0

b,0

e,0

e

α,1

e,0

e,0

Y1Y2Y3

Scegliamo arbitrariamente 5 codifiche binarie per i 5 stati della tabella degli stati:

IN

y1y2y3

z A

B

C

IN

y1y2y3

000

000

001

001

010

010

011

011

100

100

A

B

C

Tabella delle eccitazioni Y1Y2Y3 y1y2y3

IN A

B

C

000

000

001

000

001

000

001

y

Y

J

K

010

0

0

0

×

1

1

×

010

000

011

000

0

011

000

001

100

1

0

×

1

100

000

100

100

1

1

×

0

J1K1,J2K2,J3K3 y1y2y3

IN A

B

C

000 001 010 011 100

Nello Scarabottolo – Architettura e reti logiche

3

Modulo 3 – U.D. 5 – Lez. 5

Chiusura

Nello Scarabottolo – Architettura e reti logiche

4

Modulo 3 – U.D. 6 – Lez. 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).

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 6 – Lez. 1

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! Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 6 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 6 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 6 – Lez. 2

Tabella degli stati

S,z

AB s

00

01

11

10

a b c d e f

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 6 – Lez. 2

Tabella delle compatibilità S,z

AB

s

00

a

-

b c,×

01

11

10

d,0 a,0 b,0 -

a,0 b,0

c c,1 d,×

-

f,×

d e,0 d,0 a,0 e e,0 d,0 f e,0

-

-

-

f,0

a,0

f,0

b c d e f a

b

c

d

e

Grafo delle compatibilità b

∨

c

b,f

b,f

d

∨

c,e

e

b,f

c,e b,f

∨

f

b,f

c,f

∨

∨

a

b

d

e

c

I gruppi di stati compatibili (a differenza di quelli indistinguibili) non sono disgiunti! Scegliamo i gruppi più convenienti (grossi). Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 6 – Lez. 2 S,z

Tabella ridotta

AB

s

00

a

-

b c,×

01

11

d,0 a,0 b,0 -

c c,1 d,×

a,0 b,0 -

d e,0 d,0 a,0 e e,0 d,0 f e,0 S,z s

10

f,× -

-

f,0

-

a,0

f,0

01

11

10

AB 00

Ora si procede come per una normale sintesi.

α c β

Tabelle delle transizioni e delle uscite S,z s

AB 00

01

11

10

α c,× β,0 α,0 α,0 c c,1 β,× β β,0

-

β,0 α,0

β,× β,0

Y1Y2 AB y1y2

00

Scegliamo arbitrariamente 3 codifiche binarie per i 3 stati della tabella degli stati: z

01

11

10

y1y2

00

00

01

01

11

11

Nello Scarabottolo – Architetture e reti logiche

AB 00

01

11

10

4

Modulo 3 – U.D. 6 – Lez. 2

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 Y1Y2

AB

y

Y

S

R

y1y2

00

01

11

10

00

01

11

00

00

0

0

0

×

0

1

1

0

01

01

11

××

11

1

0

0

1

11

11

11

00

11

1

1

×

0

S1R1,S2R2

AB

y1y2

00

01

11

10

00 01 11

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 3 – U.D. 6 – Lez. 2

Sintesi della rete La tabella delle eccitazioni consente la sintesi combinatoria delle 4 funzioni: S1 R1 S2 R2

= = = =

f f f f

(A, (A, (A, (A,

B, B, B, B,

y1, y1 , y1, y1 ,

y2 ) y 2) y2 ) y 2)

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'autoanello di 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.

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 3 – U.D. 6 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

7

Modulo 3 – U.D. 6 – Lez. 3

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 S

Y1Y2 AB

AB s

00

01

11

10

y1y2

00

01

11

10

a

c

a

a

c

00

11

00

00

11

b

c

b

b

b

01

11

01

01

01

c

c

a

d

c

11

11

00

10

11

d

c

b

d

c

10

11

01

10

11

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).

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 3 – U.D. 6 – Lez. 3

Corse e corse critiche La corsa (malfunzionamento transitorio) è un passaggio fra due stati associati a due codifiche delle variabili di stato a distanza di Hamming maggiore di 1. I diversi ritardi di commutazione dei bistabili portano 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 Hamming unitaria 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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 3 – U.D. 6 – Lez. 3

Grafo delle adiacenze Nodi: gli stati della macchina. Archi: le connessioni fra le possibili coppie di stato presente e stato prossimo.

S

AB s

00

01

11

10

a

c

a

a

c

b

c

b

b

b

c

c

a

d

c

d

c

b

d

c

Codifiche ridondanti Nel nostro esempio, servono 3 variabili di stato (con 2, infatti, non riusciamo a garantire le necessarie adiacenze).

y2y3 y1

00

01

11

10

0 1

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 3 – U.D. 6 – Lez. 3

Tabella degli stati ridondanti S

AB

s 00

01

11

10

y2y3

a

c

a

a

c

y1

b

c

b

b

b

0

c

c

a

d

c

1

d

c

b

d

c S

00 01 11 10 a

c

d1

b

d2

AB s

00

01

11

10

a b c d1 d2

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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 3 – U.D. 6 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 3 – U.D. 6 – Lez. 4

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

Nello Scarabottolo – Architettura e reti logiche

1

Modulo 3 – U.D. 6 – Lez. 4

Diagramma degli stati

Tabella degli stati S,z

AB s

00

01

11

10

a b c d e f g h i l

Nello Scarabottolo – Architettura e reti logiche

2

Modulo 3 – U.D. 6 – Lez. 4

Tabella degli stati S,z

AB s

00

01

11

10

a

f,0

a,0

b,0

-

b

-

c,×

b,0

g,0

c

d,1

c,1

i,1

-

d

d,1

c,1

-

e,1

e

f,×

-

i,1

e,1

f

f,0

a,0

-

g,0

g

f,0

-

h,0

g,0

h

-

a,0

h,0

g,0

i

-

c,1

i,1

l,1

l

d,1

-

i,1

l,1

Tabella e grafo delle compatibilità b a,c c d

∨

e

d,f

f

∨

d,f

a,c

g b,h b,h

∨

h b,h a,c

∨

i

∨

e,l

e,l

l

∨

e,l

d,f

c

d

e

a

b

∨

∨ f

Nello Scarabottolo – Architettura e reti logiche

g

h

i

3

Modulo 3 – U.D. 6 – Lez. 4

Tabella degli stati ridotta

S,z

AB s

00

01

11

10

a b α d e β

Tabella degli stati ridotta

S,z

AB s

00

01

11

10

a

β,0

a,0

b,0

-

b

-

α,×

b,0

β,0

α

d,1

α,1

α,1

α,1

d

d,1

α,1

-

e,1

e

β,×

-

α,1

e,1

β

β,0

a,0

β,0

β,0

Nello Scarabottolo – Architettura e reti logiche

4

Modulo 3 – U.D. 6 – Lez. 4

Grafo delle adiacenze e scelta codifiche

y2y3 y1

00

01

11

10

0 1

Tabella degli stati ridondanti

S,z

AB s

00

01

11

10

a1 a2 b α d1 d2 e β

Nello Scarabottolo – Architettura e reti logiche

5

Modulo 3 – U.D. 6 – Lez. 4

Tabella degli stati ridondanti

S,z

AB s

00

01

11

10

a1

a2 , 0

a1 , 0

b,0

-

a2

β,0

a2 , 0

a1 , 0

-

b

-

α,×

b,0

β,0

α

d1 , 1

α,1

α,1

α,1

d1

d1 , 1

α,1

-

d2 , 1

d2

d2 , 1

d1 , 1

-

e,1

e

β,×

-

α,1

e,1

β

β,0

a2 , 0

β,0

β,0

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)

Nello Scarabottolo – Architettura e reti logiche

6

Modulo 3 – U.D. 6 – Lez. 4

Chiusura

Nello Scarabottolo – Architettura e reti logiche

7

Modulo 5 – U.D. 1 – Lez. 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 CC

RU U C

I RI

B

E

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 5 – U.D. 1 – Lez. 1

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 fotoresist dove non richiesto 4. Drogaggio 5. Rimozione del fotoresist

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 1 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

Wafer

3

Modulo 5 – U.D. 1 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 5 – U.D. 1 – Lez. 2

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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 5 – U.D. 1 – Lez. 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

GND 7

6

5

4

3

2

1

8

9

10

11

12

13

14

Vcc

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 1 – Lez. 2

4 2-input NAND

GND 7

6

5

4

3

2

1

8

9

10

11

12

13

14

Vcc

1 8-input NOR

GND 6

5

4

3

2

7

8

9

10

11

1

12

Vcc

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 5 – U.D. 1 – Lez. 2

2 JK flip-flop

GND 6

5

4

3

J y C K y

7

8

2

1

J y C K y

9

10

11

12

Vcc

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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 5 – U.D. 1 – Lez. 2

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à.

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 5 – U.D. 1 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 5 – U.D. 2 – Lez. 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

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 5 – U.D. 2 – Lez. 1

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 CS

I2

I1

I0

O7

O6

O5

O4

O3

O2

O1

O0

0

×

×

×

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

1

1

0

0

1

0

0

0

0

0

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

1

0

1

1

0

0

0

0

1

0

0

0

1

1

0

0

0

0

0

1

0

0

0

0

1

1

0

1

0

0

1

0

0

0

0

0

1

1

1

0

0

1

0

0

0

0

0

0

1

1

1

1

1

0

0

0

0

0

0

0

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 2 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 5 – U.D. 2 – Lez. 1

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 5 – U.D. 2 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 5 – U.D. 2 – Lez. 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 CS

A1

A0

D3

D2

D1

D0

O

0

×

×

×

×

×

×

0

1

0

0

×

×

×

0

0

1

0

0

×

×

×

1

1

1

0

1

×

×

0

×

0

1

0

1

×

×

1

×

1

1

1

0

×

0

×

×

0

1

1

0

×

1

×

×

1

1

1

1

0

×

×

×

0

1

1

1

1

×

×

×

1

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 2 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 5 – U.D. 2 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 5 – U.D. 2 – Lez. 3

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

Serial IN

D3

y3

C3

D2

y2

C2 y

3

D1

y1

C1 y

2

D0

y0

Serial OUT

C0 y

1

y

0

Clock

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 5 – U.D. 2 – Lez. 3

Struttura dello shift register • Componente sequenziale; • ogni colpo di clock, i bit contenuti nei bistabili di 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).

Parallel IN 3

Parallel IN 2

Parallel IN 1

Parallel IN 0

Load/Shift

Serial IN

D3

y3

C3

D2

y2

C2 y

3

D1

y1

C1 y

2

D0

y0

Serial OUT

C0 y

1

y

0

Clock

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 2 – Lez. 3

Varianti dello shift register

(2)

Shift register a scorrimento bilaterale (Left/Right).

Left OUT Left IN

Left/Right

Right IN

D3

y3

C3

D2

y2

C2 y3

D1

y1

C1 y2

D0

y0

Right OUT

C0 y1

y0

Clock

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 5 – U.D. 2 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 5 – U.D. 2 – Lez. 4

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

Q0

Q1

y0 C

T1

T0 y

0

Q2

y1 T2 y

1

Nello Scarabottolo – Architetture e reti logiche

Q3

y2

y3 T3

y

2

y

3

1

Modulo 5 – U.D. 2 – Lez. 4

Counter: diagramma temporale

Q3 Q2 Q1 Q0 C

1 0 1 0 1 0 1 0 1 0 tempo

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 2 – Lez. 4

Varianti del counter

(1)

Counter a caricamento parallelo (per conteggi a partire da valori qualsiasi). Parallel Load 0

Parallel Load 1

Count/Load J0

y0

Q0

J1

T0 K0

Parallel Load 2

y1

Q1

J2

K1

0

y2

Q2

J3

T2

T1 y

Parallel Load 3

y

K2

1

y3

Q3

T3 y

K3

2

y

3

C

Varianti del counter

(2)

Counter bidirezionale (Up/Down)

Up/Down

y0 C

T0 y

0

Q0

y1 T1 y

1

Nello Scarabottolo – Architetture e reti logiche

Q1

y2 T2 y

2

Q2

y3 T3

Q3

y

3

3

Modulo 5 – U.D. 2 – Lez. 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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 5 – U.D. 3 – Lez. 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 5 – U.D. 3 – Lez. 1

ROM

VCC

2 n =8 linee di prodotto

I2

I1

I0

n=3 Ingressi

U1

U0

m=2 Uscite

ROM Sezione AND: • genera tutti i mintermini di una funzione a n ingressi; • 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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 3 – Lez. 1

Caratteristiche della ROM ☺ Ha una struttura regolare, indipendente dalla configurazione della sezione OR. ☺ Le due sezioni AND e OR sono costituite da diodi realizzati 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

VCC

2 n =8 linee di prodotto

I2

I1

I0

n=3 Ingressi

Nello Scarabottolo – Architetture e reti logiche

U1

U0

m=2 Uscite

3

Modulo 5 – U.D. 3 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 5 – U.D. 3 – Lez. 1

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).

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 5 – U.D. 3 – Lez. 1

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"... Nello Scarabottolo – Architetture e reti logiche

6

Modulo 5 – U.D. 3 – Lez. 1

Chiusura

Nello Scarabottolo – Architetture e reti logiche

7

Modulo 5 – U.D. 3 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 5 – U.D. 3 – Lez. 2

PLA

VCC

p < 2 n linee di prodotto

I2

I1

I0

n=3 Ingressi

U1

U0

m=2 Uscite

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 3 – Lez. 2

Caratteristiche della PLA J Ha una struttura regolare, indipendente dalla configurazione delle sezioni AND e OR. J Le due sezioni AND e OR sono entrambe programmabili mediante bruciatura dei fusibili in serie ai diodi. J 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"... Nello Scarabottolo – Architetture e reti logiche

3

Modulo 5 – U.D. 3 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 5 – U.D. 3 – Lez. 3

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).

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 5 – U.D. 3 – Lez. 3

PAL

VCC

p < 2 n linee di prodotto

I2

I1

I0

n=3 Ingressi

U1

U0

m=2 Uscite

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. Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 3 – Lez. 3

Schema della PAL Increment 0 1 2 3

4

8

10

12

14

16

18

20

24

27

1

23

2 First fuse numbers

0 28 56 84

22

112 140

21

168 196

20

224 252

19

280 308

18

336 364

17

392 420

16

448 476 504 532

15

3

4

5

6

7

8

9

10

14

11

13

Dettagli schema PAL Increment 0 1 2 3

4

8

10

12

14

16

18

20

24

27

1

23

2 First fuse numbers

0 28 56 84

22

• Ogni ingresso entra diritto e negato. • 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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 5 – U.D. 3 – Lez. 3

Caratteristiche della PAL J Ha una struttura regolare, indipendente dalla configurazione delle sezioni AND e OR. J La sola sezione AND è programmabile mediante bruciatura dei fusibili in serie ai diodi. J La sintesi è: • ottimizzata SP (implicanti); • per reti a singola uscita, perché ogni implicante è collegato a un'unica uscita.

J Il segnale elettrico deve attraversare un solo livello di fusibili (AND), quindi la PAL risulta più veloce della PLA.

PAL a stadio di uscita programmabile Linea prodotto Linea prodotto

D Q

Mux

Pin

Linea prodotto

• Possibilità di programmare un piedino a essere ingresso o uscita, a polarità diritta o negata. • 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. Nello Scarabottolo – Architetture e reti logiche

4

Modulo 5 – U.D. 3 – Lez. 3

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. Nello Scarabottolo – Architetture e reti logiche

5

Modulo 5 – U.D. 3 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 5 – U.D. 3 – Lez. 4

Lezione 4 – Cenni a componenti EPLD 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 5 – U.D. 3 – Lez. 4

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 multiplexer necessari 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 riconfigurano dinamicamente in base alle esigenze operative (evolvable hardware). Nello Scarabottolo – Architetture e reti logiche

2

Modulo 5 – U.D. 3 – Lez. 4

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

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 5 – U.D. 3 – Lez. 5

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) =

∑ (0,1,6,7,9,11,12,15) 1

Nello Scarabottolo – Architettura e reti logiche

1

Modulo 5 – U.D. 3 – Lez. 5

Struttura interna della PAL

VCC

I4

I3

I2

I1

I0

U1

U0

Sintesi della funzione combinatoria yz wx

00

01

11

10

00

1

1

0

0

01

0

0

1

1

11

1

0

1

0

10

0

1

1

0

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

Nello Scarabottolo – Architettura e reti logiche

2

Modulo 5 – U.D. 3 – Lez. 5

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

Nello Scarabottolo – Architettura e reti logiche

3

Modulo 5 – U.D. 3 – Lez. 5

Struttura interna della PLA VCC

I3

I2

I1

I0

U2

U1

U0

Programmazione della PLA VCC

Nello Scarabottolo – Architettura e reti logiche

4

Modulo 5 – U.D. 3 – Lez. 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.

Nello Scarabottolo – Architettura e reti logiche

5

Modulo 5 – U.D. 3 – Lez. 5

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.

Nello Scarabottolo – Architettura e reti logiche

6

Modulo 5 – U.D. 3 – Lez. 5

Chiusura

Nello Scarabottolo – Architettura e reti logiche

7

Modulo 6 – U.D. 1 – Lez. 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

CPU

• Struttura del sistema digitale più importante

• Modalità di funzionamento del circuito digitale più importante

Vedremo poi come realizzare il calcolatore … Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 1 – Lez. 1

Schema della macchina di Von Neumann

CPU

Memoria

Interfaccia

di lavoro

di I/O

IN

OUT

Bus di Sistema

Elementi della macchina di Von Neumann CPU Unità master che gestisce in modo sequenziale il sistema. Memoria di lavoro Contenitore 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).

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 1 – Lez. 1

Funzionamento della CPU

Acquisisce da memoria il codice della prossima istruzione da eseguire

Fase di fetch

Interpreta il codice appena acquisito

C0 Esegue istruzione

I0

Fase di decodifica

C1 Esegue istruzione

I1

(1)

Cn Esegue istruzione

In

Fase di esecuzione

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 decodifica: • interpreta la stringa di bit come istruzione macchina.

Fase di esecuzione: • svolge quanto richiesto; • accede all'esterno per scambiare dati.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 1 – Lez. 1

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 Linee di Interconnessione Indirizzi

Memoria di lavoro i linee Parola di memoria

Dati L S

d linee

1 linea

1 linea

Array di "celle" contenenti ciascuna una parola. La singola cella è individuata dal proprio indirizzo. Nello Scarabottolo – Architetture e reti logiche

4

Modulo 6 – U.D. 1 – Lez. 1

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 Memoria

ruolo Master: decide quando e cosa fare ruolo Slave: risponde alle richieste della CPU

Interazione calcolatore-mondo esterno CPU e memoria di lavoro sono autosufficienti ma misantrope... E’ necessario: • poter inserire in memoria di lavoro i programmi da eseguire; • inserire i dati da elaborare e prelevare i risultati.

Il mondo esterno al calcolatore non è elettronico: altri fenomeni fisici e biologici (noi...)

Servono interfacce fra mondo elettronico del calcolatore e mondo esterno (periferia...) Nello Scarabottolo – Architetture e reti logiche

5

Modulo 6 – U.D. 1 – Lez. 1

Struttura dell'interfaccia di I/O

COMANDO UNITA` DI CONTROLLO INTERFACCIA

STATO DATO-IN DATO-OUT

Periferica

Bus di Sistema

Interfaccia di I/O Si presenta alla CPU simile alla memoria: contiene alcune "celle" o registri (COMANDO, STATO, DATOIN, DATO-OUT).

Interagisce con la periferica secondo quanto richiesto dalla periferica stessa: l'unità di controllo dell'interfaccia è progettata appositamente per 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.

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 6 – U.D. 1 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

7

Modulo 6 – U.D. 1 – Lez. 2

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

UNITÀ MASTER

UNITÀ SLAVE

DATA BUS ( d linee = parallelismo d ) ADDRESS BUS (a linee = 2a spazio di indirizzamento) CONTROL BUS (es. linee R e W )

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 1 – Lez. 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... Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 1 – Lez. 2

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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 1 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 6 – U.D. 2 – Lez. 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 CU

GPR

PC

Program Counter A

Control

General

Unit

Purpose Registers

B

C

ALU F

R

CC

Condition Codes

IR

Instruction Register

MAR

Memory Address Reg.

MDR

Memory Data Register

Data Bus Address Bus Control Bus

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 2 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 2 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 2 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 6 – U.D. 2 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 6 – U.D. 2 – Lez. 2

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 CU

GPR

PC

R0 (16 bit)

16 bit

R1 (16 bit) R2 (16 bit)

Control

R3 (16 bit)

Unit

R4 (16 bit)

A

B

C

ALU

R5 (16 bit)

F

R6 (16 bit) R7 (16 bit)

IR 16 bit (4+12)

CC

NZP (3 bit)

MAR 16 bit

O

MDR 16 bit

Data Bus (16 bit) Address Bus (16 bit) Control Bus (2 bit)

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 2 – Lez. 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

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 2 – Lez. 2

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 LEA

15

14

13

12

1

1

1

0

11

10

9

8

7

6

DR

5

4

3

2

1

0

pgoffset9

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).

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 2 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 6 – U.D. 2 – Lez. 3

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

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 2 – Lez. 3

CPU e memoria all'inizio del programma

Dopo istruzione 1 LEA R1, x30F4 ;carica 30F4 in R1

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 2 – Lez. 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

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 2 – Lez. 3

Dopo istruzione 4 AND R2, R2, x0000

;azzera R2

Dopo istruzione 5 ADD R2, R2, x0005

;inizializza R2 a 5

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 6 – U.D. 2 – Lez. 3

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 6 – U.D. 2 – Lez. 3

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

loop

finish

LEA

R0, table

;carica 3008 in puntatore

AND

R2, R2, #0

;azzera totalizzatore

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

ST

R2, result

;scrive risultato in memoria

table

;vettore di numeri

result

;risultato

CPU e memoria all'inizio del programma

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 6 – U.D. 2 – Lez. 3

Dopo la lettura del primo numero

Dopo la prima esecuzione del ciclo

Nello Scarabottolo – Architetture e reti logiche

7

Modulo 6 – U.D. 2 – Lez. 3

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 software che ci consentono queste attività.

Nello Scarabottolo – Architetture e reti logiche

8

Modulo 6 – U.D. 2 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

9

Modulo 6 – U.D. 3 – Lez. 1

Lezione 1 – Linguaggio Assembly 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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 3 – Lez. 1

Struttura del linguaggio Assembly Label Label

Opcode

Operands

;comments

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:

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'.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 3 – Lez. 1

Pseudo-istruzioni: quali sono .orig .fill

consente di segnalare all'Assembler da quale indirizzo di memoria caricare il programma. 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

bBBBBBBBBBBBBBBBB

16 bit codificati come 0 o 1, preceduti dal carattere 'b'. Esadecimale xEEEE 4 cifre esadecimali (0÷9, a, b, c, d, e, f minuscole o maiuscole) precedute dal simbolo 'x'. Decimale

#DDDDD

fino a 5 cifre decimali, precedute dal carattere '#', eventualmente seguito dal segno '-'.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 3 – Lez. 1

Un esempio Ritorniamo al secondo programma presentato nella Lez.3, U.D.2 di questo modulo (l'esempio sulle istruzioni di controllo):

loop

finish table result

.orig LEA AND LDR BRZ ADD ADD BRNZP ST .blkw .fill .blkw .end

x3000 R0, table R2, R2, #0 R1, R0, #0 finish R2, R2, R1 R0, R0, #1 loop R2, result #4 #0 #1

;carica inizio tabella in punt. ;azzera totalizzatore ;legge prossimo numero ;se nullo ha finito ;somma a totalizzatore ;incrementa puntatore ;prossimo numero ;scrive risultato in memoria ;vettore di numeri ;risultato

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...

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 6 – U.D. 3 – Lez. 1

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 6 – U.D. 3 – Lez. 2

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...

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 3 – Lez. 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. symbol table

value x3008

Possibili segnalazioni di errore Errori sintattici

istruzioni o pseudo-istruzioni scritte 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... Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 3 – Lez. 2

La tabella dei simboli prodotta Ecco il contenuto del file .sym prodotto dall'Assembler: // Symbol table // Scope level 0: // Symbol Name // ---------------// finish // loop // result // table

Page Address -----------3007 3002 300D 3008

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 3 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 6 – U.D. 3 – Lez. 3

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...

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 3 – Lez. 3

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 bottone Step program o il tasto F8 ci fanno avanzare di una istruzione alla volta. Andiamo a vedere come funziona... Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 3 – Lez. 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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 3 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 6 – U.D. 4 – Lez. 1

Lezione 1 – Programmazione interattiva Architetture e reti logiche Modulo 6 - Linguaggio macchina Unità didattica 4 - Sviluppo di programmi per la CPU 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 4 – Lez. 1

Simulazione di programmi interattivi Se un programma fa uso delle routine di I/O: • TRAP x21 • TRAP x23

scrittura caratteri; 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. Non sono disponibili altre modalità di I/O: per esempio per ricevere o emettere valori numerici. Perché non le scrivete voi? Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 4 – Lez. 1

Chiusura

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 4 – Lez. 2

Lezione 2 – Esempi di programmi LC-2 Architetture e reti logiche Modulo 6 - Linguaggio macchina Unità didattica 4 - Sviluppo di programmi per la CPU 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. Nell'ISA LC-2 non esiste un'istruzione di shift. 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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 4 – Lez. 2

Primo esempio: modulo shift.asm Vediamo la struttura delle due routines: • shl • shr

trasla di un bit a sinistra il valore in R0; 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...

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 4 – Lez. 2

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 programma istruzione 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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 4 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 6 – U.D. 4 – Lez. 3

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 la CPU 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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 4 – Lez. 3

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 CPU LC-2. • Questo consente: - l'annidamento delle chiamate; - la programmazione ricorsiva.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 4 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 4 – Lez. 4

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 la CPU 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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 6 – U.D. 4 – Lez. 4

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=i AND R5,R5,#0 ;for (i=1;...) ADD R5,R5,#1; checks for end of i-for loop loopi LD R0,maxi ;for (...;i<=MAXi;...) NOT R0,R0 ADD R0,R0,#1 ADD R0,R0,R5 BRP endi ;starts body of i-for loop ..... ..... ;exits from i-for loop endi

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 6 – U.D. 4 – Lez. 4

if (isprime==TRUE) {...}; else {...}; ;checks second if condition LD R0,isprime ;if (isprime == TRUE) BRZ elseif2 ;"then" branch of second if selection LD R0,ascii ;printf ("...prime...") ..... ..... BRNZP endif2 ;"else" branch of second if selection elseif2 LD R0,ascii ;printf ("...NOT prime...") ..... ..... ;exits from second if selection endif2

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).

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 6 – U.D. 4 – Lez. 4

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 7 – U.D. 1 – Lez. 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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 1 – Lez. 1

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 Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 1 – Lez. 1

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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 1 – Lez. 1

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 7 – U.D. 2 – Lez. 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)

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 2 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 2 – Lez. 1

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 nd 1 1 1 1

ma md CS R/W OE RD

• 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).

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 2 – Lez. 1

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...

VCC

2 n =8 linee di prodotto

I2

I1

I0

n=3 Ingressi

Nello Scarabottolo – Architetture e reti logiche

U1

U0

m=2 Uscite

4

Modulo 7 – U.D. 2 – Lez. 1

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 nd 1 1 1

ma md CS OE RD

• 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).

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 7 – U.D. 2 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 7 – U.D. 2 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 2 – Lez. 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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 2 – Lez. 2

Come realizzare celle da 16 bit

Data Bus (DB15÷DB0) 16

DB15÷DB8

8

md

DB7÷DB0

8

md

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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 2 – Lez. 2

Come realizzare un banco da 4K Address Bus (AB15÷AB0) 16 Data Bus (DB15÷DB0) 16

AB9÷AB0

DB15÷DB8

DB7÷DB0

AB11-AB10 10 8 1

10 8 1

ma md CS

10

ma md CS

10

ma md CS

10

ma md CS

10

8 1

8 1

ma md CS

ma md CS

Decoder I1 I0

O3 O2 O1 O0

10 8 1

10 8 1

8 1

8 1

ma md CS

ma md CS

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 Select del decoder; – solo in questo caso, una riga del banco di memoria viene abilitata a interagire con la CPU.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 7 – U.D. 2 – Lez. 2

Come posizionare il banco da 4K Address Bus (AB15÷AB0) 16 Data Bus (DB15÷DB0) 16

AB9÷AB0

DB15÷DB8

DB7÷DB0

AB11-AB10 10

AB15÷AB12

8 1

10 8 1

ma md CS

10

ma md CS

10

ma md CS

10

ma md CS

10

8 1

8 1

ma md CS

ma md CS

Decoder I1 I0 CS

O3 O2 O1 O0

10 8 1

10 8 1

8 1

8 1

ma md CS

ma md CS

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...).

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 7 – U.D. 2 – Lez. 2

Segnali di controllo Address Bus (AB15÷AB0) 16 Data Bus (DB15÷DB0) 16 R W

AB9÷AB0

DB15÷DB8

DB7÷DB0

AB11-AB10 10

AB15÷AB12

8 1 1

10 8 1 1

Decoder O3 O2 O1 I0 O0 CS

ma md CS R/W

10

ma md CS R/W

10

ma md CS R/W

10

ma md CS R/W

10

8 1 1

8 1 1

ma md CS R/W

ma md CS R/W

I1

10 8 1 1

10 8 1 1

8 1 1

8 1 1

ma md CS R/W

ma md CS R/W

Attenzione alle variazioni dei segnali ! Address Bus (AB15÷AB0) Data Bus (DB15÷DB0) 16 R W

AB9÷AB0

16

DB15÷DB8

DB7÷DB0

AB11-AB10 10

AB15 ÷ AB12

8 1 1

10 8 1 1

Decoder O3 O2 O1 I0 O0 CS

ma md CS R/W

10

ma md CS R/W

10

ma md CS R/W

10

ma md CS R/W

10

8 1 1

8 1 1

ma md CS R/W

ma md CS R/W

I1

10 8 1 1

10 8 1 1

Nello Scarabottolo – Architetture e reti logiche

8 1 1

8 1 1

ma md CS R/W

ma md CS R/W

6

Modulo 7 – U.D. 2 – Lez. 2

Segnali di controllo diversi AB9÷AB0

Address Bus (AB15÷AB0) 16 Data Bus (DB15÷DB0) 16 Read/Write MemAccess

DB15÷DB8

DB7÷DB0

AB11-AB10 10

AB15 ÷ AB12

8 1 1

10 8 1 1

Decoder I1 I0 CS

O3 O2 O1 O0

10 8 1 1

10 8 1 1

ma md CS R/W

10

ma md CS R/W

10

ma md CS R/W

10

ma md CS R/W

10

8 1 1

8 1 1

8 1 1

8 1 1

ma md CS R/W

ma md CS R/W

ma md CS R/W

ma md CS R/W

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. Nello Scarabottolo – Architetture e reti logiche

7

Modulo 7 – U.D. 2 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

8

Modulo 7 – U.D. 3 – Lez. 2

Lezione 2 – Controllo di programma Architetture e reti logiche Modulo 7 - Architettura del calcolatore Unità didattica 3 - Input/Output a controllo di programma Nello Scarabottolo Università degli Studi di Milano - Ssri - CDL ONLINE

Struttura dell'interfaccia di I/O Ricordiamo quanto visto nella Lez.1, U.D.1 del Modulo 6: COMANDO UNITA` DI CONTROLLO INTERFACCIA

STATO DATO-IN DATO-OUT

Periferica

Bus di Sistema

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 3 – Lez. 2

Schema del controllo di programma START

ON -> COMANDO.attesa_tasto STATO.tasto_premuto = TRUE ?

NO

SI

DATO-IN -> registro_CPU STATO.video_libero = TRUE ?

NO

SI

registro_CPU -> DATO-OUT ON -> COMANDO.visualizza_carattere END

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. 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à. Serve però un Sistema Operativo multitasking, che gestisca la ripartizione del tempo di CPU fra attività (processi o task) differenti. Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 3 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 3 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 7 – U.D. 3 – Lez. 1

Lezione 1 – Problematica delle operazioni di Input/Output Architetture e reti logiche Modulo 7 - Architettura del calcolatore Unità didattica 3 - Input/Output a controllo 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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 3 – Lez. 1

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: •• controllo di programma (vince il clock); •• interrupt (vince l'orologio); • Direct Memory Access o DMA (indipendenti).

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).

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 3 – Lez. 1

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 connessi con 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 connessi con questa attività "autonoma".

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 3 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 7 – U.D. 4 – Lez. 1

Lezione 1 – Principio di funzionamento dell'interrupt Architetture e reti logiche Modulo 7 - Architettura del calcolatore Unità didattica 4 - Input/Output a interrupt 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 4 – Lez. 1

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. Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 4 – Lez. 1

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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 4 – Lez. 1

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 7 – U.D. 4 – Lez. 2

Lezione 2 – Interrupt cablato

Architetture e reti logiche Modulo 7 - Architettura del calcolatore Unità didattica 4 - Input/Output a interrupt 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 polling delle interfacce: • ogni interfaccia deve essere interrogata per sapere se è la responsabile dell'interruzione; • l'ordine di interrogazione è associato all'urgenza della periferica. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 4 – Lez. 2

Daisy chain

CPU

Interf.1 INTIN

Interf.2 INTIN

INTOUT INTREQ

Interf.n INTIN

INTOUT INTREQ

VCC INTOUT

INTREQ

Rpull-up

INTACK INTREQ

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. Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 4 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 4 – Lez. 3

Lezione 3 – Interrupt vettorizzato

Architetture e reti logiche Modulo 7 - Architettura del calcolatore Unità didattica 4 - Input/Output a interrupt 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 4 – Lez. 3

Vantaggi e problemi J 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. Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 4 – Lez. 3

Funzionamento del PIC

CPU

PIC

I/O INTERFACE READY

COMANDO

IMR CONTROL UNIT CPU

CONTROL UNIT PIC

IPR IVR

STATO CONTROL UNIT I/O INTERFACE

DATO-IN DATO-OUT

IntVect

Data Bus Address Bus Control Bus

INTACK INTREQ

Registri del PIC Registri accessibili alla CPU come normali registri di interfaccia (componente programmabile): IVR

IPR

Interrupt Vector Register: contiene l'identificativo associato a ciascuna periferica collegata; 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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 4 – Lez. 3

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 riprogrammando il registro IMR.

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 7 – U.D. 5 – Lez. 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 5 – Lez. 1

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 passo cosa 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). Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 5 – Lez. 1

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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 5 – Lez. 1

Funzionamento del DMAC

Memoria

CPU

DMAC

I/O INTERFACE IN

TD

READY

DC CONTROL UNIT CPU

CONTROL UNIT DMAC

HOLDACK

PA MDA

Address

INTREQ INTACK S

COMANDO STATO

CONTROL UNIT I/O INTERFACE

DATO-IN DATO-OUT

Data

Data Bus Address Bus Control Bus

HOLDREQ

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).

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 7 – U.D. 5 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 7 – U.D. 5 – Lez. 2

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)

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 7 – U.D. 5 – Lez. 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. Nello Scarabottolo – Architetture e reti logiche

2

Modulo 7 – U.D. 5 – Lez. 2

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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 7 – U.D. 5 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 8 – U.D. 1 – Lez. 1

Lezione 1 – Data Path di 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...

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 8 – U.D. 1 – Lez. 1

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...

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 8 – U.D. 1 – Lez. 1

ISA della CPU NS-0 LOAD

15

14

0

0

13

12

11

10

9

8

7

6

5

4

3

2

1

0

5

4

3

2

1

0

ind14

M(ind14) → R0 STORE

15

14

0

1

13

12

11

10

9

8

7

6

ind14

R0 → M(ind14) ADD

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

6

5

4

3

2

1

0

val16

R0 + val16 → R0 BRZ

15

14

1

1

13

12

11

10

9

8

7

ind14

if (Z ≠ 0) then ind14 → PC

Struttura interna della CPU NS-0 C A

ALU F Z (1 bit)

B CC

R0 (16 bit) 14 bit

Input Internal Bus

16 bit (2+14) 14 bit 16 bit

GPR

CU

PC IR MAR

MDR

Output1 Internal Bus Output2 Internal Bus

O

Data Bus (16 bit) Address Bus (14 bit) Control Bus (2 bit)

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 8 – U.D. 1 – Lez. 1

Input Internal Bus

D

Q

D

Rn-1

C

Q

Rn-2

C

D

R1

Q

D

C

R0

Q

C

RIN

ROUT1

Output1 Internal Bus

Registri della CPU NS-0

Input Internal Bus

D

Q

MDR n-1 C

MDR

IN

MDR

SAMPLE

D

Q

MDR0 C

MDR

OUT1

MDR

Output1 Internal Bus

Registro MDR della CPU NS-0

OE

Data Bus

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 8 – U.D. 1 – Lez. 1

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) Significato MSB 0 0 1 1

LSB 0 1 0 1

NOP PASS INC ADD

(O=A) (O=A+1) (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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 8 – U.D. 1 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 8 – U.D. 1 – Lez. 2

Lezione 2 – Control Path di 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 8 – U.D. 1 – Lez. 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 C A

ALU F Z (1 bit)

B CC

R0 (16 bit) 14 bit

Input Internal Bus

16 bit (2+14) 14 bit 16 bit

GPR

CU

PC IR MAR

MDR

Output1 Internal Bus Output2 Internal Bus

O

Data Bus (16 bit) Address Bus (14 bit) Control Bus (2 bit)

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 8 – U.D. 1 – Lez. 2

S1: MAROE , MEMR , ALUNOP C A

ALU F Z (1 bit)

B CC GPR

R0 (16 bit)

IR

16 bit (2+14) Input Internal Bus

CU

PC

14 bit

MAR

14 bit

MDR

16 bit

Output1 Internal Bus Output2 Internal Bus

O

Data Bus (16 bit) Address Bus (14 bit) Control Bus (2 bit)

S2: MAROE , MEMR , MDRSAMPLE , ALUNOP C A

ALU F Z (1 bit)

B CC

R0 (16 bit) 14 bit

Input Internal Bus

16 bit (2+14) 14 bit 16 bit

GPR

CU

PC IR MAR

MDR

Output1 Internal Bus Output2 Internal Bus

O

Data Bus (16 bit) Address Bus (14 bit) Control Bus (2 bit)

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 8 – U.D. 1 – Lez. 2

S3: MDROUT1 , ALUPASS , IRIN C A

ALU F Z (1 bit)

B CC GPR

R0 (16 bit)

IR

16 bit (2+14) Input Internal Bus

CU

PC

14 bit

MAR

14 bit

MDR

16 bit

Output1 Internal Bus Output2 Internal Bus

O

Data Bus (16 bit) Address Bus (14 bit) Control Bus (2 bit)

S4: PCOUT1 , ALUINC , PCIN C A

ALU F Z (1 bit)

B CC

R0 (16 bit) 14 bit

Input Internal Bus

16 bit (2+14) 14 bit 16 bit

GPR

CU

PC IR MAR

MDR

Output1 Internal Bus Output2 Internal Bus

O

Data Bus (16 bit) Address Bus (14 bit) Control Bus (2 bit)

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 8 – U.D. 1 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 8 – U.D. 1 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 8 – U.D. 1 – Lez. 2

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. Nello Scarabottolo – Architetture e reti logiche

7

Modulo 8 – U.D. 1 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

8

Modulo 8 – U.D. 2 – Lez. 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 8 – U.D. 2 – Lez. 1

Struttura della CU cablata counter Clock decoder

S9 S8 S7 S6 S5 S4 S3 S2 S1 S 0 decoder

B A S L

Z

CC

IR 15

14

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).

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 8 – U.D. 2 – Lez. 1

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 J Una struttura particolarmente efficiente. J Assicura la massima velocità di esecuzione. J 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 Logic Array. L Solo recentemente, grazie all'evoluzione tecnologica, è applicabile a CU complesse.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 8 – U.D. 2 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 8 – U.D. 2 – Lez. 2

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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 8 – U.D. 2 – Lez. 2

Struttura della CU microprogrammata

microprogram counter

memoria di microprogramma

microistruzione generatore del prossimo indirizzo

microcomandi

prossimo indirizzo

Z (CC ) IR15 IR14

condizioni di salto

comandi a registri, ALU, Control Bus (Output CU)

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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 8 – U.D. 2 – Lez. 2

Microprogramma mA MAR 0 1 2 3 4 5 LOAD 6 7 8 9 10 STORE 11 12 13 14 ADD 15 16 17 18 19 BRZ 20 21

FETCH

MDR

IR

PC

IN

OE

IN

OUT1

SAM

OE

IN

OUT1

IN

1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0

0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

R0

O U T 1 IN

1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0

Z

ALU

MEM J JNZ J15 J14 mA

OUT1

OUT2

SAM

M SB

LSB

R

W

0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0

1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1

0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

10 15

0 20

0

0 0 0

Caratteristiche della CU microprogrammata J Una struttura particolarmente regolare. J Particolarmente adatta a CU complesse (CISC) con tecnologia hardware non evoluta. J Sfrutta le tecniche di progettazione software. J 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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 8 – U.D. 2 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 8 – U.D. 3 – Lez. 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 8 – U.D. 3 – Lez. 1

Struttura dell'ALU A

B

C

ALU

R

F

• 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).

Struttura interna dell'ALU

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 8 – U.D. 3 – Lez. 1

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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 8 – U.D. 3 – Lez. 1

Chiusura

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 8 – U.D. 3 – Lez. 2

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

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.

A1 B1

A B R

HA S

Nello Scarabottolo – Architetture e reti logiche

R2

FA

R1

S1 1

Modulo 8 – U.D. 3 – Lez. 2

Somma di 2 numeri a n bit A n-1 Bn-1

Rn

FA

A2 B2

R n-1

FA

R3

Sn-1

A1 B1

R2

FA

S2

A 0 B0

R1

FA

S1

S0

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).

Carry look ahead - espressione logica Espressione logica del riporto (i+1)esimo: Ri+1

= AiRi + BiRi + AiBi

Fattorizziamo nel modo seguente:

ovvero: dove:

Iterando:

Ri+1

= AiBi + (Ai + Bi)Ri

Ri+1

= Gi + PiRi

Gi = AiBi

Generate function

Pi = Ai + Bi

Propagate function

Ri+1

= Gi + PiGi-1 + PiPi-1Ri-1

Ri+1

= Gi + PiGi-1 + PiPi-1Gi-2 + + PiPi-1...P1G0 + PiPi-1...P0R0

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 8 – U.D. 3 – Lez. 2

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 Bn-1

B2

B1

B0 ADD/SUB

A n-1

Rn

FA Sn-1

A2

R n-1

R3

FA S2

A1

R2

FA S1

A0

R1

FA S0

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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 8 – U.D. 3 – Lez. 2

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 8 – U.D. 3 – Lez. 3

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 1

1

0

1

Moltiplicando M (13)

1

0

1

1

Moltiplicatore Q (11)

1

1

0

1

1

1

0

1

0

0

0

0

1

1

0

1

0

0

0

1

×

1

1

1

Nello Scarabottolo – Architetture e reti logiche

1

Prodotto P (143)

1

Modulo 8 – U.D. 3 – Lez. 3

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. Nello Scarabottolo – Architetture e reti logiche

2

Modulo 8 – U.D. 3 – Lez. 3

Schema circuitale della cella

ppi

mj

qi

qi

Rout

R in

FA

mj

ppi+1

Schema circuitale della matrice 0

m3

0

m2

0

m1

0

m0 q0 0

q1

p0

0

q2

p1

0

q3

p2

0 p7

p6

p5

p4

Nello Scarabottolo – Architetture e reti logiche

p3

3

Modulo 8 – U.D. 3 – Lez. 3

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!

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 8 – U.D. 3 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 9 – U.D. 1 – Lez. 1

Lezione 1 – Principio di funzionamento della memoria cache Architetture e reti logiche Modulo 9 - Principali linee di evoluzione architetturale Unità didattica 1 - Memoria cache e gerarchia di memoria Nello Scarabottolo Università degli Studi di Milano - Ssri - CDL ONLINE

Un grafico di qualche anno fa... MHz 160 140 CPU 120 DRAM

Pentium (100 MHz)

100 80 Pentium

60 40 20 0

486 8086

286

386

8088 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98

anno

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 9 – U.D. 1 – Lez. 1

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 funzionassero con una memoria di lavoro 10 volte più lenta della CPU ???

Cosa serve davvero alla CPU? indirizzo generato dalla CPU xFFFF

x0000 tempo

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 9 – U.D. 1 – Lez. 1

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. Nello Scarabottolo – Architetture e reti logiche

3

Modulo 9 – U.D. 1 – Lez. 1

Perché dal 1982? Processore

Anno

Costo

8086

1978

-

286

1982

386

MIPS iniziali

MIPS massimi

n° transistor

0.33

0.75

29 K

$8

1.20

2.66

134 K

1985

$ 91

5.00

11.40

275 K

486

1989

$ 317

20.00

54.00

1.2 M

Pentium

1993

$ 900

112.00

3.1 M

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 cache a 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 al processore - qualche centinaio di KB. E se le cose degenerano...: • cache L3 (di terzo livello) esterna al processore - qualche decina di MB! Nello Scarabottolo – Architetture e reti logiche

4

Modulo 9 – U.D. 1 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 9 – U.D. 1 – Lez. 2

Lezione 2 – Memoria cache e politica Tag Associative Architetture e reti logiche Modulo 9 - Principali linee di evoluzione architetturale Unità didattica 1 - Memoria cache e 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. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 9 – U.D. 1 – Lez. 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 tag

MC

MdL

0

1

Blocco × Gruppo 0

Blocco 0

B0G0

1

0

Blocco × Gruppo 1

Blocco 1

B0G1

:

:

:

:

:

:

Blocco × Gruppo 127

Blocco 127

B0G127

Blocco 128

B1G0

Blocco 129

B1G1

127

31

00000 0000000 0000 00000 0000000 1111 00000 0000001 0000 00000 0000001 1111

00000 1111111 0000 00000 1111111 1111 00001 0000000 0000 00001 0000000 1111 00001 0000001 0000 00001 0000001 1111

: : Blocco 255

B1G127

Blocco 256

B2G0

00001 1111111 0000 00001 1111111 1111 00010 0000000 0000 00010 0000000 1111

: : Blocco 4095

Nello Scarabottolo – Architetture e reti logiche

11111 1111111 0000

B31G12711111 1111111 1111

2

Modulo 9 – U.D. 1 – Lez. 2

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: NB = N° blocco nel gruppo

NG = N° gruppo di blocchi

NP = N° parola nel blocco

5 bit → 25=32 blocchi per gruppo

7 bit → 27=128 gruppi (blocchi di cache)

4 bit → 24=16 parole × blocco

Ricerca parola in cache Tag Associative Address Bus: NB & NG & NP

yes

HIT CPU ↔ MC [NG & NP]

no

tag [NG] = NB ?

MISS BloccoMdL [NB & NG] → BloccoMC [NG] NB → tag [NG] CPU ↔ MC [NG & NP]

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 9 – U.D. 1 – Lez. 2

Caratteristiche Tag Associative J 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...

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 9 – U.D. 1 – Lez. 2

Chiusura

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 9 – U.D. 1 – Lez. 3

Lezione – Politiche Fully Associative e Set Associative Architetture e reti logiche Modulo 9 - Principali linee di evoluzione architetturale Unità didattica 1 - Memoria cache e 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...

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 9 – U.D. 1 – Lez. 3

Politica Fully Associative tag

MC

MdL

0

4095

Blocco 0

Blocco 0

1

1

Blocco 1

Blocco 1

:

:

:

:

:

:

Blocco 127

:

127

i

Blocco i : : : Blocco 4095

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: NBMdL = N° blocco in MdL

NP = N° parola nel blocco

12 bit → 212=4096 blocchi in MdL

4 bit → 24=16 parole × blocco

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 9 – U.D. 1 – Lez. 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

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 9 – U.D. 1 – Lez. 3

Ricerca parola in cache Fully Associative Address Bus: NBMdL & NP found

NBMC = ASS(NBMdL).tag

not found

MISS HIT CPU ↔ MC [NBMC & NP] counters++ 0 → counter [NBMC]

NBMC = ASS(11...11).counter BloccoMdL [NBMdL] → BloccoMC [NBMC] NBMdL → tag [NBMC] CPU ↔ MC [NBMC & NP] counters++ 0 → counter [NBMC]

Caratteristiche Fully Associative J 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.

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 9 – U.D. 1 – Lez. 3

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. Nello Scarabottolo – Architetture e reti logiche

5

Modulo 9 – U.D. 1 – Lez. 3

Chiusura

Nello Scarabottolo – Architetture e reti logiche

6

Modulo 9 – U.D. 1 – Lez. 4

Lezione 4 – Accesso in scrittura alla memoria cache Architetture e reti logiche Modulo 9 - Principali linee di evoluzione architetturale Unità didattica 1 - Memoria cache e 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. Cosa facciamo dell'originale in MdL? Abbiamo due possibilità: • Politica store thru: – si modifica il dato sia in MC sia in MdL. • Politica store in: – si modifica il dato soltanto in MC. Nello Scarabottolo – Architetture e reti logiche

1

Modulo 9 – U.D. 1 – Lez. 4

Politica Store Thru J 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 J 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 MdL prima 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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 9 – U.D. 1 – Lez. 4

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

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 9 – U.D. 1 – Lez. 5

Lezione 5 – Gerarchia di memoria

Architetture e reti logiche Modulo 9 - Principali linee di evoluzione architetturale Unità didattica 1 - Memoria cache e gerarchia di memoria Nello Scarabottolo Università degli Studi di Milano - Ssri - CDL ONLINE

Gerarchia di memoria CPU

pochi registri GPR

L1 cache

qualche KB

L2 cache

qualche centinaio di KB

Memoria di Lavoro

qualche centinaio di MB

Memoria di massa a disco

Memoria di backup ottica o a nastro

Nello Scarabottolo – Architetture e reti logiche

qualche decina di GB

centinaia di GB a basso costo

1

Modulo 9 – U.D. 1 – Lez. 5

Rapporto fra gli ultimi due livelli Memoria 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 cache soprastanti) è una memoria: • di natura elettronica → tempi di lavoro in linea con quelli della CPU; • ad accesso casuale → ogni cella richiesta è accessibile nello stesso tempo (cache permettendo...). 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.

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 9 – U.D. 1 – Lez. 5

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 parzialmente caricata 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.

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 9 – U.D. 1 – Lez. 5

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 di Sistemi Operativi.

Abbiamo inventato la memoria ideale! Costo per bit

Memorie a semiconduttore bipolari Memorie a semiconduttore MOS

Dischi magnetici Dischi ottici Nastri

Memoria ideale Tempo di accesso

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 9 – U.D. 1 – Lez. 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

Nello Scarabottolo – Architetture e reti logiche

5

Modulo 9 – U.D. 2 – Lez. 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)

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 9 – U.D. 2 – Lez. 1

Funzionamento di una CPU normale

fase della Control Unit I0 Write Back

I1 WB1

WB0

Exec

E1

E0

Decode

D1

D0

Fetch

F1

F0

tempo

Funzionamento di una CPU pipeline

Control Unit attive I0

F0

I3

I4

WB1

WB2

WB3

WB4

E0

E1

E2

E3

E4

E5

D0

D1

D2

D3

D4

D5

D6

F1

F2

F3

F4

F5

F6

F7

ECU

FCU

I2

WB0

WBCU

DCU

I1

tempo

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 9 – U.D. 2 – Lez. 1

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

FCU Fetch Control Unit

DCU Decode Control Unit

ALU

PC MAR

MDR

ECU Exec Control Unit

IR

WBCU Write Back Control Unit

GPR

SP

Data Bus Address Bus Control Bus

Nello Scarabottolo – Architetture e reti logiche

3

Modulo 9 – U.D. 2 – Lez. 1

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

Nello Scarabottolo – Architetture e reti logiche

4

Modulo 9 – U.D. 2 – Lez. 2

Lezione 2 – Problemi di esecuzione di 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.

Nello Scarabottolo – Architetture e reti logiche

1

Modulo 9 – U.D. 2 – Lez. 2

Control dependency svuotamento della pipeline

Control Unit attive I0 WBCU

WB0

ECU DCU FCU

I4

F0

E0

E1

D0

D1

D2

F1

F2

F3

WB20

F20

E20

E21

D20

D21

D22

F21

F22

F23 tempo

I0: BR I20

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...).

Nello Scarabottolo – Architetture e reti logiche

2

Modulo 9 – U.D. 2 – Lez. 2

Branch Prediction Table (BPT) Branch address

Branch destination

Statistics

0

20

T

• Quando FCU incontra istruzione di salto, consulta Branch address; • se aveva già incontrato l'istruzione, si adegua a Statistics (Taken / Not taken) e eventualmente salta a Branch destination; • 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.

Data dependency R0 azzerato da AND

Control Unit attive I0 WBCU

FCU

F0

I2

I3

I4

WB0

WB1

WB2

WB3

WB4

E0

E1

E2

E3

E4

E5

D0

D1

D2

D3

D4

D5

D6

F1

F2

F3

F4

F5

F6

F7

ECU DCU

I1

tempo

I0: AND R0,R0,#0 I1: ADD R1,R1,R0 Nello Scarabottolo – Architetture e reti logiche

R0 richiesto da ADD

3

Modulo 9 – U.D. 2 – Lez. 2

Data forwarding ECU inoltra il dato dove richiesto (a se stessa)

FCU

DCU

Fetch Control Unit

Exec Control Unit

Write Back Control Unit

ALU

GPR

PC MAR

MDR

WBCU

ECU

Decode Control Unit

IR

SP

Data Bus Address Bus Control Bus

Resource dependency ECU accede a memoria per leggere var

Control Unit attive

I0 WBCU

FCU

F0

I2

I3

WB0

WB1

WB2

WB3

E0

E1

E2

E3

E4

D0

D1

D2

D3

D4

D5

F1

F2

F3

F4

F5

F6

ECU DCU

I1

tempo

I0: LD R0,var I1: AND R1,R1,#0 I2: ADD R1,R0,R0 Nello Scarabottolo – Architetture e reti logiche

FCU accede a memoria per fetch di I2

4

Modulo 9 – U.D. 2 – Lez. 2

Macchina di Harvard CPU

Variables cache Variables Control Bus Variables Address Bus Variables Data Bus

FCU

ECU MAR

DCU

Fetch Control Unit

Decode Control Unit

MDR

Exec Control Unit

ALU

PC MAR

MDR

IR

WBCU

Write Back Control Unit

GPR

SP

Instructions Data Bus Instructions Address Bus Instructions Control Bus

Instructions cache System Control Bus System Address Bus System Data Bus

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. Nello Scarabottolo – Architetture e reti logiche

5

Modulo 9 – U.D. 2 – Lez. 2

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! Nello Scarabottolo – Architetture e reti logiche

6