Appunti di Calcolatori elettronici

Matilde Simonini ingegneria informatica anno 2021/2022

Appunti di calcolatori elettronici

Calcolatore: concetto e modelli

Il calcolatore è inteso come un esecutore universale di programmi (algoritmi espressi in un linguaggio di programmazione). Turing ha cercato in primis di fornire una modellizzazione matematica del calcolatore. In sostanza, secondo il suo modello, un calcolatore è una macchina che riceve dei dati espressi come una sequenza di simboli e stabilisce, secondo un programma e una volta letto un simbolo, se spostarsi a destra o sinistra e cosa scrivere nella casella in cui si trova, portando anche con sé un concetto di stato. Il numero di stati del calcolatore è finito. In questo senso il calcolatore viene visto come una funzione che riceve in input una sequenza di simboli che restituisce un’altra sequenza di simboli.

In termini informali una MdT è composta da un nastro, una testina di lettura e scrittura (I/O), un'unità di memoria interna, un'unità di calcolo e un'unità logica. Il nastro è lo strumento che contiene le informazioni. Si tratta di un dispositivo teoricamente illimitato. Il nastro è suddiviso in celle, ciascuna delle quali può contenere un solo simbolo appartenuto ad un certo insieme finito, che prende il nome di alfabeto di lavoro. Il nastro contiene quindi le informazioni che devono essere elaborate, i risultati intermedi e quelli finali.

La testina di lettura e scrittura è un meccanismo posizionato su una casella del nastro e governato da un’unità di controllo. Può leggere il simbolo che vi è contenuto e se necessario sovrascriverlo con un altro appartenente all’insieme di lavoro. La testina può spostarsi a destra o sinistra di una cella oppure può restare ferma. Ogni simbolo scritto viene delimitato da un carattere speciale. L’unità logica è quella a cui spetta la decisione dei passi da compiere che necessita di conoscere il contenuto della cella sulla quale è attualmente posizionata la testina di lettura e scrittura e lo stato corrispondente della macchina. Data questa coppia di valori l’unità logica fornisce una terna di valori che coincide con l’istruzione da eseguire: il valore che deve essere sovrascritto nella cella, il nuovo stato della macchina, la direzione che la testina deve prendere.

Nessun calcolatore moderno è riuscito a superare la capacità di calcolo e le funzioni espresse dal modello di Turing. Un linguaggio viene detto Turing-completo quando è in grado di sviluppare tutte le operazioni delineate dalla macchina di Turing.

In questo corso però non ci si occupa di modelli teorici ma di calcolatori fisici. Il primo calcolatore fisico è un calcolatore a vapore: la cosiddetta macchina analitica. Un oggetto che riceveva in ingresso i dati attraverso le schede perforate. L’unità di elaborazione era basata su una macchina a vapore. Comparvero diversi problemi tecnologici riguardo la realizzazione del progetto. La scrittura del primo programma per questo calcolatore (un programma Turing-completo) fu Ada Lovelace.

Calcolatori elettronici attuali

In questo corso ci si occupa di calcolatori basati su tecnologie elettroniche. I calcolatori attuali sono basati sulla rappresentazione di cifre binarie (0,1) attraverso segnali elettrici oppure attraverso tecnologie magnetiche e ottiche. Il fatto che noi, attualmente, possiamo rappresentare qualunque cosa attraverso le cifre binarie (falso, vero) trova le basi nella teoria, nello studio di George Boole, nel quale venne formulata l’Algebra booleana.

Classi di calcolatori elettronici

• Desktop: quelli dedicati all’uso personale
• Server: destinati a grossi carichi di lavoro. Tipicamente hanno molti task da eseguire.
• Embedded computer: calcolatori incapsulati in dispositivi fisici. Calcolatori che svolgono compiti precisi in un dispositivo più complesso, ad esempio un dispositivo meccanico.

Architettura di un calcolatore elettronico

ISA (Instruction Set Architecture)

Costituisce l’interfaccia tra l’hardware e il livello più basso del software. Il livello ISA (Instruction Set Architecture) descrive l'architettura delle istruzioni che la CPU è in grado di eseguire in Hardware (Firmware). Specifica tutto ciò che i programmatori devono sapere per produrre programmi in linguaggio macchina corretti: istruzioni in linguaggio macchina (formato, semantica), dispositivi I/O, ...

Una stessa architettura (ISA) può avere implementazioni diverse! Alcune architetture (ISA) attuali: IA-32 (Intel, AMD), MIPS, PowerPC, ARM, …

Perché anche ad ingegneria informatica?

• Motivi culturali e base per corsi successivi
  • Come un programma di alto livello viene tradotto in linguaggio macchina?
  • Come il linguaggio macchina viene eseguito dall’hardware?
  • Quali fattori influenzano le performance di un calcolatore?
• Influenza nella performance dei livelli inferiori
  • Le prestazioni di un programma (alto livello) sono determinate da:
  • Il programma stesso
  • Prestazioni dell’hardware nell’eseguire le istruzioni dell’ISA
  • Il compilatore, che può produrre software “ottimizzato” per l’hw sottostante
• Necessità pratica di “sporcarsi le mani” in assembler
  • Nei sistemi embedded: riduzione lunghezza del codice (costo) + vincoli real-time
  • In un approccio ibrido, per codificare parti del programma “time critical” (es: superamento delle convenzioni nella codifica di procedure)
  • Per utilizzare istruzioni specializzate che un compilatore potrebbe non sfruttare
  • In alcuni calcolatori non è disponibile un linguaggio di alto livello!

Citazioni illustri

I confini tra hardware e software sono sfumati: Hardware and software are logically equivalent (Andrew Tanenbaum) Hardware is just petrified software (Karen Panetta Lenz).

ma "dovendo scegliere": È vero che il software non potrebbe esercitare i poteri della sua leggerezza se non mediante la pesantezza dell’hardware; ma è il software che comanda, che agisce sul mondo esterno e sulle macchine, le quali esistono solo in funzione del software, si evolvono in modo d'elaborare programmi sempre più complessi. (Italo Calvino).

Richiami: il modello di Von Neumann

Il programma del corso

Reti logiche: reti combinatorie

Il livello più basso, come visto, è quello dell’elettronica che costituisce la base del funzionamento dei calcolatori.

Livelli hardware

• Livello del layout: trattato nei corsi di microelettronica
• Livello circuitale: trattato nei corsi di elettronica digitale.

  Il livello circuitale riguarda argomenti come l’ottenere dal collegamento di transistor dei componenti logici significativi (es. porte logiche) e, a livello più alto, l’interpretazione di livelli di tensione come valori logici (es: tensione alta “1”, bassa “0”). Esistono molte famiglie logiche che corrispondono a modalità diverse di realizzazione sulla base di:

  • Transistor utilizzato (es. BiPolar, MOSFET, ecc.)
  • Modo di utilizzare i transistor (collegandoli tra loro)

  Esempio: CMOS inverter (è una famiglia logica). La parte sottolineata in giallo riguarda quindi il dominio dell’elettronica. Nel livello layout vengono utilizzati dei modelli per comprendere come costruire quelli che vengono chiamati transistors, che possono essere concepiti come degli interruttori che permettono di creare una tensione. L’elettronica digitale vera e propria studia come collegare i transistor per ottenere delle porte logiche.

Livelli hardware: logico

I mattoni fondamentali sono le porte logiche, di cui a questo livello non interessano le caratteristiche elettriche, ma solo la dipendenza tra valori binari in ingresso e il valore binario in uscita. Porta logica = dispositivo fisico che realizza un elemento di calcolo binario.

Caratteristiche:

 numero prefissato di linee di ingresso (es. 2 porte per AND)  una sola linea di uscita. Alcuni parametri inerenti al livello circuitale e fisico:  assorbimento di energia (quantità)  ritardo di propagazione: velocità della risposta da parte della porta (dall’istante di ingresso, all’istante di uscita)  immunità dal rumore. In questo corso l’unico parametro considerato sarà il ritardo di propagazione mentre gli altri verranno trascurati. Una porta logica, in elettronica digitale e informatica, è un circuito digitale in grado di implementare (cioè di realizzare, simulandone la "logica matematica" mediante opportuni controlli su segnali elettrici) una particolare operazione logica di una o più variabili booleane.

In base al numero di ingressi, che rappresentano il numero di variabili che una porta logica può ricevere in input, le porte logiche si possono classificare in:

• Porte a due variabili: AND, OR, XOR, NOR, NAND e XNOR
• Porte a singola variabile: NOT

Nota bene: l’insieme di porte logiche di riferimento dipende dalla famiglia logica utilizzata e da considerazioni progettuali (inerenti al livello circuitale e del layout).

Convenzione: 1 = vero; 0 = falso.

Una porta AND ha un’uscita y = 1 soltanto quando entrambi gli ingressi valgono 1, mentre in tutti gli altri casi si ha y = 0. Il significato di AND corrisponde a quello della congiunzione italiana “e”. La porta OR corrisponde alla congiunzione italiana “o”. Questa porta restituisce 1 se almeno un valore di ingresso ha valore 1. La porta XOR ha lo stesso significato dell’espressione latina “out-out”: date due proposizioni logiche A e B, la disgiunzione esclusiva tra le due proposizioni è vera soltanto nel caso in cui è vera solo una delle due proposizioni. La porta NOT è poi una porta unaria che inverte il valore dell’ingresso. La porta NAND corrisponde ad una AND negata e la stessa cosa vale per la porta NOR e la porta OR. Le porte AND, NOR e NOT possono essere realizzare solo a partire da AND, OR, NAND.

Rete logica

È un dispositivo che ha un determinato numero di ingressi e un determinato numero di uscite, dove le uscite dipendono dagli ingressi, ma il viceversa non è vero, gli ingressi sono indipendenti. Ci sono due tipi di reti logiche:

• Combinatorie: ogni uscita dipende soltanto dalla combinazione degli ingressi attuali. Una rete logica di questo tipo realizza una vera e propria funzione in cui l’uscita è funzione degli ingressi.
• Sequenziali: l’uscita dipende dagli ingressi e dallo stato, che sintetizza la storia (successione degli ingressi che ha avuto nel passato). Si tratta di un’estensione della rete combinatoria.

Specifica e realizzazione di reti combinatorie

Reti combinatorie

Sono definite come un circuito elettronico in grado di “calcolare” una funzione booleana (a valori binari di una o più variabili binarie). La rete combinatoria è interpretata come una scatola nera: Ci sono due aspetti nella progettazione di reti combinatorie:

• La specifica della rete, che consiste sostanzialmente nella descrizione del comportamento desiderato dalla rete combinatoria, ossia bisogna specificare la funzione che deve realizzare.
• La realizzazione

Specifica del comportamento di una rete combinatoria

Significa specificare per ogni uscita una funzione booleana ): {0,1} {0,1}. f( , … , f : →0 −1 Esistono due modi per specificare una funzione booleana:

• Tabella di verità: elenca, per ognuna delle possibili combinazioni (dei valori) degli ingressi, il valore corrispondente della funzione.
• Espressione booleana: utilizzando operatori logici, esprime il legame tra le variabili di uscita (corrispondenti alle uscite) e le variabili di ingresso (corrispondenti agli ingressi). Fornisce una dipendenza algebrica ed è fondamentale perché da questa è possibile passare al disegno del circuito in modo immediato.

Nota bene: per ogni funzione esistono infinite espressioni booleane che vi corrispondono.

Esempio: specifica di una rete combinatoria

Con tabella di verità (Nota bene: op indica l’operazione da effettuare tra OR e AND): Per ogni combinazione degli ingressi è stato stabilito cosa deve valere l’uscita.

Con espressione booleana:

Regole sulle espressioni booleane

1. Le costanti 0 e 1 e le variabili (simboli a cui possono essere associati i valori 0 e 1) sono espressioni booleane.
2. Se E1 ed E2 sono espressioni booleane lo sono anche (E1), (E2) e (E1 + E2).
3. Non esistono altre espressioni oltre a quelle che possono essere generate da un numero finito di applicazioni delle regole 1 e 2.

Esempi:

• ((E1 + E2) · E3)
• ((E1 · E2) + ((E3 · E4) + E5 · E6))

Nota bene: come nelle espressioni aritmetiche, ha la priorità su +. Il passaggio dall’espressione booleana alla tabella di verità risulta essere banale. Il passaggio dalla tabella di verità all’espressione booleana non è banale ed è di fondamentale importanza per la sintesi con porte logiche.

Come passare dalla tabella all’espressione booleana?

Si parte dalle righe della tabella in cui C vale 1. Consideriamo tutte le righe della tabella di verità in cui C. Scriviamo C come somma di mintermini, ossia come somma di termini costituiti dal prodotto fra OP, A e B presi come sono se nella tabella valgono 1 oppure complementari se valgono 0. Mintermine: funzione booleana che assume il valore 1 in corrispondenza di una e una sola configurazione degli ingressi. Si ottiene quindi = forma canonica disgiuntiva.

C = OP · A · B + OP · A · ¬B + A · B · ¬C

Ad ogni espressione booleana di variabili corrisponde un’unica funzione booleana di variabili (una tabella!!!). Per ogni funzione booleana di variabili: infinite espressioni booleane di variabili. Nota bene: la stessa operazione può essere fatta attraverso l’uso dei maxtermini: è possibile ottenere C come somma di termini, ognuno dei quali viene ricavato dalle righe in cui C vale 0. Ogni termine è costituito dal prodotto fra OP, A e B presi come sono se valgono 0, altrimenti vengono negati.

Caso: funzione a più uscite

Una funzione a uscite e ingressi si può trattare come funzioni a ingressi, una per ogni uscita: tabelle di verità hanno colonne di uscita o specifica con espressioni booleane: una per ogni uscita. Finora abbiamo parlato di come specificare il comportamento di una rete combinatoria, senza preoccuparci di “come è fatta”. A questo livello, “come è fatta” una rete logica significa “da quali componenti HW è fatta” e come questi sono collegati. Vedremo come sintetizzare una rete utilizzando una combinazione di porte logiche. Altre possibilità: ROM (Read Only Memory), PLA, … Supponiamo di avere a disposizione le tre porte AND, OR, NOT per vedere come realizzare una rete logica con questi componenti. Nel momento in cui si hanno a disposizione le porte ci si deve ricondurre ad un’espressione booleana relativa alle uscite possibili, dati i vari ingressi, per poi raffigurare il circuito di porte logiche che permettono di avere quel determinato comportamento.

Sintesi con porte logiche elementari

Risulta essere immediata se si parte da un’espressione booleana. Nel caso di si ha una porta di OR con due ingressi. Ma non è necessario basarsi sulla forma canonica.

Semplificazione di reti combinatorie

Ci si chiede come trovare la forma minima, ossia l’espressione booleana che porta ad una minimizzazione del circuito. I passaggi fatti fino ad esso sono: tabella di verità → espressione booleana → circuitale. In realtà noi stiamo trascurando tutta la parte elettronica che sta dietro i ragionamenti che facciamo. Le minimizzazioni a livello logico non per forza rimangono realizzabili anche quando si va a costruire il circuito nella pratica (es. in presenza di porte NAND). Data una funzione da realizzare si vuole quindi derivare l’espressione “minima”: l’espressione che porta ad una realizzazione con il numero minimo di elementi di calcolo e che dipende dalla tecnologia. Ci sono due modi di agire nella semplificazione:

• Semplificare l’espressione booleana
• Agire sulla tabella di verità che consenta di ottenere un’espressione più semplice

I due metodi sono equivalenti.

Algebra di Boole

È lo strumento matematico usato per lo studio delle reti combinatorie espresse mediante formule booleane. È un particolare tipo di algebra che include:

• Un insieme di supporto (l’insieme {0,1} nel nostro caso)
• Degli operatori binari: AND (·) e OR (+)
• Un operatore complemento: NOT (¬)

Gli operatori soddisfano certe proprietà che si deducono da un insieme di assiomi. L’insieme su cui opera l’algebra di Boole è un insieme finito: 0,1. In ogni caso gli operatori AND, OR e NOT possono essere definiti in maniera assiomatica, ossia sono operatori che soddisfano alcuni assiomi.

Nota: la prima colonna si può derivare dalla seconda (e viceversa).