Test completo per Architettura degli Elaboratori

Informatica: comprensione di problemi risolvibili con algoritmi

A.A. 2016/2017
Enrico Martini VR406823
Prof. Franco Fummi

Esecutore problema algoritmo automatico

Architettura: materia che studia la tecnica che trasforma un algoritmo in hardware dedicato (es. computabilità, NP-completezza). Più è complesso l’algoritmo, più è complesso l’hw dedicato. Negli anni l’hw è diventato sempre più generico, con un sw dedicato e più specifico alle esigenze.

Assembly: linguaggio utilizzato in architettura, più facilmente comprensibile all’HW.

Intervallo di campionamento

Qualsiasi grandezza può essere definita con una funzione rispetto al tempo. Il tempo per utilità deve essere campionato, così si può osservare la funzione in punti (la frequenza di campionamento si calcola facendo il reciproco dell’intervallo di campionamento): Hz_f = 1/Δt. Ogni grandezza ha un intervallo di campionamento diverso.

Discretizzazione

Si passa dai numeri reali ad approssimazioni a seconda dell’esigenza. La funzione originale diventa così una spezzata poligonale.

Teorema di Shannon

Dato un errore piccolo a piacere, esiste sempre una frequenza di campionamento e un intervallo di discretizzazione minore di ε. L’evoluzione del sistema digitale dipende dall’informazione di base.

I numeri sono rappresentati in notazione posizionale. I sistemi digitali usano il codice binario (noi usiamo il sistema decimale). I numeri vengono quindi convertiti in bit per essere manipolati dal sistema digitale.

Codifica

Processo che associa informazioni a codici binari. Quanti bit è necessario usare?

• n = Bit
• M = informazioni
• n = log₂ M

Il processo di codifica tiene conto di:

• Velocità di codifica/decodifica
• Impatto sul sistema digitale

Codifiche standard

Usate per interpretare il codice binario allo stesso modo e non perdere il significato. Per i caratteri alfanumerici esistono i caratteri ASCII (256 informazioni → 8Bit (1Byte)). Per i numeri esistono codifiche diverse:

• Interi assoluti “modulo”
• Interi relativi “modulo + segno”, “complemento a 2”
• Razionali “standard a virgola mobile”, “standard a virgola fissa”

Codifica modulo

Es: n = 57
nBit = 6 5 4 3 2 1 0
Codice binario: 57 = 111001

Tavola per le conversioni di base

Codifica modulo + segno

Poco usata perché è presente sia il “-0” e “+0”.

Codifica del complemento a 2

Per fare il contrario bisogna calcolare l’opposto:

• -10
• 111 7
• Se il numero da compilare è maggiore del campo di esistenza, il sistema va in overflow.

Codifica a virgola fissa (numeri razionali)

Compromesso tra grandezza dei numeri e precisione. Utile per i sistemi embedded. Nella maggioranza dei casi il numero convertito viene approssimato.

Codifica a virgola mobile (floating point)

Codifica di riferimento: IEEE754-1985 ± m ⋅ b^e
Simboli: m=mantissa b=base e=esponente

Quale base

Si è voluto usare la base 2 per facilitare lo shift a sx e dx della mantissa (*2 o /2).

Codifica della mantissa

La forma normalizzata della mantissa consiste in:

• La prima cifra significativa a sx deve essere 1 (1.xxxxxxxxx)
• Codifica a virgola fissa
• Shift a sx -1 all’esponente, Shift a dx +1 all’esponente

Il segno della mantissa è un bit da aggiungere a sx del bit più significativo (0/+,1/-).

Codifica dell’esponente

Codifica per 127 “eccesso”, ∞00000000 -127 ≈ -∞.

Quanti bit utilizzare

Viene codificato per primo il segno, poi l’esponente e la mantissa. Della mantissa si omette la parte intera (1.) e si codifica solo la parte frazionaria. I comuni sono:

• Ampiezza precisione: Nome in C, Mantissa, Esponente
• 32 Singola Float 23 8
• 64 Doppia Double 52 11

Codici errore e numeri particolari

• 1/0 + 31 zeri → ±0 ∞
• 1/0 + esponente 8 uno + mantissa 23 zeri → ± Not a Number (NaN)
• 1/0 + esponente 8 uno + mantissa con almeno un 1 → NaN (specifiche algoritmi)

Modello

Modello = ambiente semplificato della realtà in cui ci si concentra sugli aspetti fondamentali.

Modello booleano

Modello perfetto per riuscire a compilare in binario l’algoritmo. Qualsiasi funzione può essere ridotta agli operatori + e * < B , * , + , { 0 , 1 } >.

Operatori fondamentali

• Prodotto (AND)
• Somma (OR)

Mintermine e on set

Mintermine = coppia di valori booleani che danno come risultato 1. On set = insieme di mintermini. Realizzando l’on set con gli operatori di base (somma di prodotti) si può avere una funzione booleana. Off set = insieme di valori che non sono mintermini.

Metodo elettrico per la rappresentazione degli operatori logici

Uso dei transistor a tecnologia CMOS:

• Transistor n: in conduzione con ΔV, in interdizione senza ΔV
• Transistor p: in conduzione senza ΔV, in interdizione con ΔV
• Porta logica: rappresentatori elettrici degli operatori