Tesina Architettura dei calcolatori

Indice

• Introduzione
• Codifiche e codifica binaria
• Codifica in modulo e segno
• Codifica in complemento a due
• Opposto del complemento a due
• Esempi di codifiche
• Esempi di decodifiche
• Notazione scientifica
• Standard IEEE 754
• Codifica alfanumerica Gramsci
• Codifica esadecimale
• Circuiti
• Algebra di commutazione
• Teorema fondamentale dell'algebra di commutazione
• Teorema fondamentale duale
• Ottimizzazione di Carnaugh
• Analisi circuitale
• Moduli combinatori
• Codificatore
• Decodificatore
• Multiplexer
• Demultiplexer
• ROM
• PLA
• Memorie
• Latch
• Flip flop
• Flip flop di tipo D
• Registri
• RAM
• Lettura/scrittura RAM
• ALU
• Aritmetica binaria
• Celle addizionatrici
• Operazioni dei circuiti ALU
• Introduzione architettura von Neumann
• Cenni di multiprogrammazione
• Istruzioni SEC-XR
• Controllo di flusso
• Microsequenze
• Architettura MIPS
• Allocazione di memoria
• Convenzioni di utilizzo dei registri
• I/O MIPS
• Assembler MIPS
• Planimetria MIPS
• Pipelining MIPS
• Prestazioni architettura
• Gerarchie di memoria
• Cache
• Prestazioni della memoria
• Input/Output
• Bus
• Cenni di programmazione
• Assembler MIPS
• Bibliografia

Introduzione

John von Neumann definì per la prima volta il concetto di elaboratore elettronico. Considerato il padre dell'informatica, fu il primo ad inquadrare, in una teoria matematica coerente, le "macchine intelligenti" e gli automi e portò a definire le basi dei moderni calcolatori, ovvero non più sofisticate calcolatrici ma veri e propri sistemi di elaborazione digitale di diversa complessità capaci di eseguire sequenze di comandi (algoritmi).

L'architettura dei calcolatori elettronici è la disciplina che si occupa della composizione e dell'ideazione di calcolatori più o meno complessi, ottenendo la massima resa prestazionale con il minimo costo possibile. Nello specifico, la composizione del sistema si basa intorno ad una derivazione del modello di Von Neumann (1944), basato su 4 componenti fondamentali: CPU, memoria, input e output.

In questa trattazione si cercherà di affrontare questi concetti evidenziando come queste componenti siano collegate tra loro, evidenziando gli aspetti fondamentali delle componenti singole e degli apparati che compongono. Si partirà dall'elaborazione ciclica dei dati, dalla loro codifica ed elaborazione circuitale, alla memorizzazione, seguendone poi il ciclo all'interno del calcolatore. Una volta introdotta le architetture di Von Neumann, SEC-XR e MIPS, si passerà alla microprogrammazione, seguita dalle gerarchie di memoria, concludendo infine con i principi della programmazione.

Codifiche e codifica binaria

Affinché un calcolatore possa comprendere i dati in ingresso, è necessario codificarli in maniera standard per renderne possibile analisi, elaborazione e memorizzazione tramite un numero finito di simboli. La codifica binaria è il più semplice dei sistemi di codifica: viene utilizzato l'alfabeto binario, ovvero composto semplicemente dai valori “1” e “0” e viene utilizzato nei dispositivi bistabili (ovvero in grado di assumere solo due configurazioni). Utilizzando K bit di memoria (il bit è il più piccolo spazio di memoria occupabile su un calcolatore) si ottengono 2^K combinazioni diverse. Sulla base di questa considerazione si è arrivati a usare i bit come unità di misura dello spazio occupato da una determinata informazione.

L'unità di misura della memoria può infatti essere espressa come:

• 8 Bit = 1 Byte
• 2¹⁰ Byte = 1 KiloByte
• 2²⁰ Byte = 1 MegaByte
• 2³⁰ Byte = 1 GigaByte

Codifica in modulo e segno

È necessario, nella codifica numerica, poter indicare sia il numero sia il segno del valore. Uno dei due metodi utilizzati per conseguire quest'obiettivo è la codifica in modulo e segno. Questa tecnica prevede che venga utilizzato il primo bit del dato per indicare il segno (0 se positivo, 1 se negativo) e i restanti bit per codificare il valore assoluto.

Esempio: 011101 = (2³ + 2² + 2⁰) = -13. Per ottenere la conversione dobbiamo sommare i valori di tutti i bit di valore 1, escluso il primo in quanto indica il segno. Viceversa, se sostituissimo il valore del primo bit con “0” otterremmo come soluzione “+13”.

Codifica in complemento a due

Abbiamo precedentemente accennato che esistono due tecniche per codificare i valori numerici. Il secondo è quello della codifica in complemento a due, che prevede di assegnare ancora una volta il compito di identificare il segno al primo bit, ma che a differenza del metodo con modulo e segno viene sommato agli altri bit. Considerando lo stesso valore preso in considerazione in precedenza otteniamo: 111101 = (2³ + 2² + 2⁰ - 2⁴) = -3.

Opposto del complemento a due

Possiamo calcolare l'opposto in complemento a due facendo il complemento di tutti i numeri al bit 1. 11101 + 1 = 00011 che in binario ha valore 3, ovvero l'opposto del valore che avevamo in partenza.

Esempi di codifiche

Un numero di parte intera può venire codificato tramite la tecnica delle divisioni successive, mentre un numero decimale può essere codificato tramite il metodo delle moltiplicazioni successive. La codifica a 4 bit in modulo e segno a base 2 del numero 30,50 è:

1. 30/2 = 15 con resto 0;
2. 15/2 = 7 con resto 1;
3. 7/2 = 3 con resto 1;
4. 3/2 = 1 con resto 1;
5. 1/1 = 1 con resto 0;

Quindi possiamo scrivere come 0010.0,50:

1. 0,50*2 = 1,00 con parte intera 1;
2. 0,00*2 = 0,00 con parte intera 0;
3. 0,00*2 = 0,00 con parte intera 0;
4. 0,00*2 = 0,00 con parte intera 0;

Quindi possiamo asserire che è 0,50 = 1000.

Esempi di decodifiche

(1231.543)₁₀ codificato in base 10 diventa:

• 0¹ 2^-1 - 2^-3 = (1 - 2^s) * (1*10⁰ + 3*10¹ + 2*10² + 5*10^-1 + 4*10^-2 + 3*10^-3) = -231.543, dove s=1;
• (0110.10)₂ codificato in base 2 diventa:
• 0¹ 2^-1 - 2^-2 = (1 - 2^s) * (0*2⁰ + 1*2¹ + 1*2² + 1*2³ + 0*2^-1) = +6.5, dove s=0;

Notazione scientifica

La notazione scientifica è degna di nota in quanto permette di esprimere in modo conciso i numeri reali utilizzando le potenze intere in base 10. Il vantaggio fondamentale è che permette di utilizzare grandezze molto grandi o molto piccole senza memorizzare lunghe sequenze di 0, infatti viene considerato un solo numero intero diverso da 0, seguito dalla sua parte decimale, moltiplicato per 10^K, con K intero che può essere sia positivo che negativo. Lo schema di rappresentazione è:

(±N.F * B^k)

Dove N rappresenta la parte intera, compresa tra 1 e B-1, F è un insieme di cifre comprese tra 0 e B^-1 e B, normalmente, è 10.

Standard IEEE 754

Lo Standard IEEE 754 specifica la codifica binaria per i numeri in notazione scientifica normalizzata. Con questo standard il numero viene espresso tramite una parola binaria da 32 bit in precisione singola e da 64 bit in precisione doppia. Un numero in virgola mobile è composto da 1 bit di segno, da un campo per l'esponente sommato alla base di polarizzazione (127) indicato con la lettera “E” ed da un campo per la mantissa.

Esempio di codifica del numero +110.524 in singola precisione (1 bit di segno, 8 bit di campo E, 23 bit per la parte frazionaria):

• Il segno del numero è positivo, ciò implica che il bit di segno è 0;
• 110.524 è codificato in 1101110.100 (col metodo delle divisioni e moltiplicazioni successive);
• Spostiamo la virgola in modo da scrivere il numero in notazione scientifica: 1.101110100 x 2⁶.

La parte frazionaria della mantissa è 10111010000000000000000 (aggiungiamo zeri per riempire tutti i 23 spazi peri bit). L’esponente è 6 e sommando alla base di polarizzazione ricaviamo il campo E in decimale (133), che codificato è pari a 10000101.

Codifica alfanumerica ASCII

La codifica ASCII è lo standard americano per la codifica di numeri, lettere e simboli. Utilizza combinazioni di 7 bit dove i primi 3 più significativi sono usati per i simboli e i rimanenti 4 per numeri e lettere in ordine alfabetico. Successivamente alla sua creazione venne proposto un nuovo standard, l'extended ASCII, che utilizza 8 bit e permette di rappresentare il doppio dei caratteri, quali vocali accentate, simboli semigrafici e simboli di uso meno comune. La lettera “A”, ad esempio, viene rappresentata come 01000001. Successore dell'extended ASCII è la codifica Unicode, a 16 bit, che permette di rappresentare fino a 1.114.112. La codifica Unicode venne creata per poter utilizzare anche caratteri, ad esempio, in cirillico o greco.

Codifica esadecimale

La codifica in esadecimale (base 16) ha sedici caratteri a disposizione (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, ove le lettere indicano i numeri da 10 a 15) per la rappresentazione dei dati. Se si vuole effettuare una codifica da binario in modulo e segno ad esadecimale (o viceversa) bisogna tener presente che ogni carattere del sistema esadecimale corrisponde a 4 bit del sistema binario.

Esempio: la codifica di “1111111100011010” è “7F1A”.

Circuiti

Gli elementi per la realizzazione delle operazioni sono i circuiti combinatori. I circuiti combinatori di base sono associati alle principali operazioni e sono identificati da porte logiche. I circuiti si distinguono per la profondità, che indica sia il numero massimo di porte collegate, in serie o in parallelo, sia il tempo che il circuito impiega per realizzare il calcolo richiesto. Tutte le porte logiche hanno un solo elemento in output che può essere un input per altre porte. Esistono 6 funzioni booleane di base: NOT, AND, OR, NOR, NAND, XOR:

• NOT: complemento di bit; ha una sola linea in input e restituisce l'inverso dell'ingresso.
• AND: prodotto logico di 2 bit; ha due linee in ingresso e una in uscita.
• OR: somma logica di 2 bit (ad eccezione del caso di input (1,1), in cui il risultato è 1); ha due linee in ingresso e una in uscita.
• NOR: funzione complementare dell'OR.
• NAND: funzione complementare dell'AND.
• XOR: detto anche OR esclusivo, esegue la somma in modulo due di 2 bit; ha due ingressi e una in uscita.

Per mezzo di queste porte possiamo effettuare operazioni che con le quali possiamo esprimere funzioni diverse. I circuiti calcolano funzioni booleane, costituite da variabili in forma vera o negata, detti letterali. Le espressioni di letterali possono essere ridotte in forme SOP canoniche o forme POS canoniche. Le forme SOP sono somme di prodotti, ossia OR di minterm. I minterm sono termini prodotto fondamentali che contengono tutte le variabili di una funzione (in forma vera o negata) e nella tabella di verità è presente un unico 1. Le forme POS sono prodotti di somme, ossia AND di maxterm. I maxterm sono termini somma fondamentali che contengono tutte le variabili di una funzione (in forma vera o negata) e nella tabella di verità presentano un unico 0. I minterm di n variabili definiscono 2ⁿ funzioni che presentano un solo 1 nella tavola di verità. I maxterm di n variabili definiscono 2ⁿ funzioni che presentano un solo 0 nella tavola di verità.

Esempio: se n è pari a 3, possiamo individuare 8 funzioni booleane e possiamo costruire una tavola di verità che verifichi la condizione espressa precedentemente. Si dice profondità della rete combinatoria la quantità di porte che il circuito è in grado di sopportare e la quantità di tempo che impiega per compiere un’operazione.

Algebra di commutazione

È possibile rappresentare i circuiti combinatori in maniera compatta grazie agli operatori dell'algebra di commutazione, ovvero:

• ¬ = Not;
• ∧ = And;
• ∨ = Or;

L'algebra di commutazione è definita dall'insieme di tutte le espressioni booleane e dalle regole di calcolo indotte sulle espressioni dagli operatori Not, And e Or.

Teorema fondamentale dell'algebra di commutazione

Una qualunque funzione booleana può essere espressa in forma SOP (l’Or delle funzioni distinte che associano un solo uno in corrispondenza di un qualche assegnazione alle variabili) canonica, ovvero come l’Or di termini prodotto (minterm) distinti, ciascuno formato dall’And di n variabili prese in forma vera o negata.

a₀ ∨ a_n-1 ∨ f(a₀,…,a_n-1)

Dimostrazione: Si consideri una funzione f di n variabili indipendenti a valori {0,1}. Se la f associa uno ad un assegnamento, la somma di prodotti, SOP canonica, comprende il minterm (reso vero), per cui vale uno. Se invece, la f associa zero ad un assegnamento, la SOP è OR di minterm, tutti uguali a zero.

Teorema fondamentale duale

Il teorema fondamentale duale spiega che le funzioni booleane si possono esprimere in forme POS, cioè come AND di maxterm distinti (ogni maxterm è dato dall’OR di n letterali). Vengono considerati i maxterm che definiscono funzioni con valore pari a 0, poiché 1 è elemento neutro per il prodotto. Lo scopo della minimizzazione è quello di trovare una forma SOP con il minimo numero possibile di termini prodotto, ovvero riducendo al minimo le porte AND e OR.

Dimostrazione: consideriamo una funzione f di n variabili indipendenti a valori in {0,1}. Se la f associa 1 ad un assegnamento, la SOP è AND di maxterm uguali a uno. Le forme SOP/POS minimali rappresentano circuiti minimali con il numero minore possibile di porte AND (OR) e, a parità di numero di porte AND, con il numero minore possibile di ingressi alle porte AND (OR). Le tecniche di ottimizzazione circuitale che esprimono le funzioni calcolate in forma SOP le riducono a forme SOP equivalenti che contengono il minor numero di implicanti.

Ottimizzazione di Carnaugh

Le tavole di verità di una funzione devono essere sviluppate facendo sì che coppie di minterm simili siano vicine tra loro. Questa rappresentazione prende il nome di mappe di Carnaugh, definite per un numero di variabili al più pari a 4. Se il numero di variabili è al più 3 avremo 2 righe, altrimenti ne avremo 4; una volta disegnate vanno completate inserendo il minterm reso vero e il valore assunto dalla funzione (f) per ogni assegnamento. Il senso di compilazione è dall'alto verso il basso e da sinistra a destra. Una volta completate, le colonne 3 e 4 vanno scambiate. Se abbiamo n variabili, il numero di minterm sarà 2ⁿ. Le caselle con un lato in comune sono dette adiacenti; inoltre devono essere considerate adiacenti anche le caselle all’estremità di una riga o di una colonna come se la mappa fosse disegnata su di una superficie chiusa su sé stessa.

Nelle mappe di Carnaugh le espressioni SOP canoniche possono essere facilmente ottenute componendo l’OR di tutti i minterm resi veri da assegnamenti su cui la funzione assume valore uno (per il Teorema Fondamentale). Le forme SOP semplificabili contengono esattamente 2^k minterms distinti, formati da tutti i termini prodotto distinti di k variabili prese in forma vera o negata. Possiamo quindi identificare gli (n-k) -cubi sulle mappe, a patto che il numero di variabili sia piccolo. Ci interessano i cubi massimali essenziali (ovvero quelli non contenuti in altri cubi formati da un numero maggiore o uguale di minterm) che contengono valori uno assunti dalla funzione e che non sono contenuti in altri cubi massimali. Individuano i termini prodotto semplificati che vanno scelti per costruire l'espressione SOP minimale.

Analisi circuitale

Come il nome suggerisce, l'analisi dei circuiti consiste nel descrivere come funziona il circuito e, essendo nota la sua configurazione, le porte logiche utilizzate. Nell'analisi si ricava la funzione applicata al circuito e si descrive ciò che il circuito si propone di fare. Per sintesi di un circuito si intende il processo opposto: dato un problema, si ricava la funzione che lo caratterizza e si definisce un circuito. Le soluzioni possono essere differenti e varieranno per costi, complessità, numero di porte logiche utilizzate, profondità del circuito. L’obiettivo principale è trovare soluzioni efficaci e semplici, definendo circuiti con profondità sempre più basse, poiché ciò implica una diminuzione del tempo impiegato per svolgere le operazioni.

Moduli combinatori

I moduli combinatori sono moduli del calcolatore i quali non si occupano di svolgere calcoli aritmetici. Questi circuiti non memorizzano informazioni, ma sostanzialmente date alcune variabili d’ingresso, l’uscita o le uscite sono solamente funzione dello stato attuale degli ingressi.

Codificatore

Il codificatore è il modulo combinatorio che realizza una funzione booleana di m bit, tutti posti a 0 tranne l’i-esimo (posto a 1), e viene definito da m-ingressi e n-uscite, numerati da 0 a m-1, tali che m=2ⁿ. A questi dispositivi possono essere associati le proprietà distributiva e complementare. I codificatori sono tipicamente impiegati quando diverse unità sono connesse a un sistema. Essi costituiscono una famiglia di reti combinatorie che trasformano, tra ingresso e uscita, parole rappresentate in un dato codice in parole rappresentate in un codice diverso.