Informazioni sul Corso (1/2)� Modalità d’esame� Prova scritta (teoria ed esercizi)� Prova orale� Le prove sono indipendenti� Ricevimento� E-mail per fissare un appuntamento� Tentativamente, Lunedì (dopo lezione, ore 12.15/13.30)
Informazioni sul Corso (2/2)� Trasparenze disponibili� Su CampusNet� http://www.ce.unipr.it� Libri di testo consigliati� Patterson, Hennessy, Struttura e Progetto dei Calcolatori, Zanichelli� Stallings, Architettura e Organizzazione dei Calcolatori, Addison Wesley� Bucci, Architettura e Organizzazione dei Calcolatori Elettronici – Fondamenti, McGraw-Hill� Hyde, The Art of Assembly Language,http://webster.cs.ucr.edu/AoA
Programma del Corso� Introduzione agli elaboratori� Storia, macchine astratte, rappresentazione e codifica dell’informazione� Livello logico� Automi a stati finiti, reti combinatorie e sequenziali� Livello assembly e micro-architettura� Architettura di una CPU, assembly, memoria, I/O� Approfondimenti sul livello assembly IA-32� Con esercizi di programmazione� Approfondimento sui compilatori� Analisi di un piccolo compilatore C-like (per IA-32)� Approfondimento sulle micro-architetture� Analisi di un semplice emulatore di micro-architettura
Informatica = Informazione + Automatica� Anche nota come� Computer science (paesi Anglosassoni)� Scienze dell’informazione (più correttamente)� Calcolatori� Strumento per la trasmissione, la trasformazione e la conservazione delle informazioni
Problemi e Soluzioni (1/3)� Elaboratori Supporto (teorico e pratico) per esprimere la soluzione di problemi� Nel vocabolario “Un problema è una ricerca che bisogna eseguire con procedimenti scientifici” –Larousse “Quesito che richiede la determinazione o la costruzione di uno o più enti che soddisfano a date condizioni fissate in precedenza” – Devoto
Problemi e Soluzioni (2/3)� Gli elaboratori non risolvono i problemi Esprimono una soluzione Sono (rapidissimi e) precisi esecutori di ordini� Risolvere un problema richiede un esecutore Stato iniziale, stato finale (risolto, non esiste
soluzione, ...) Criterio di verifica� Attività del risolutore del problema èricercare una sequenza di ordini da far compiere ad un esecutore
Processo di Risoluzione Processo di risoluzione� Una sequenza di passaggi da uno stato iniziale, a stati successivi finché non si perviene ad uno stato finale che rappresenta una soluzione Ricerca di una sequenza di azioni che
conduce � Dalla conoscenza di informazioni iniziali� Alla conoscenza di certe informazioni finali che soddisfino ad un criterio di verifica
Istruzioni ed Esecuzione� La ricerca delle azioni è sostanzialmente diverso dall’esecuzione delle azioni che portano dai dati ai risultati
Azioni = Istruzioni + Esecutore� Il risolutore deve usare un linguaggio per comunicare le istruzioni all’esecutore Con lo scopo di fargli eseguire le corrispondenti
Risoluzione di un Problema� Risolvere un problema significa Ricercare ed esprimere (in un linguaggio) un elenco di istruzioni che, una volta interpretate da un esecutore, conducono (partendo da alcune informazioni iniziali) a delle informazioni finali soddisfacenti un criterio di verifica� Uno stesso elenco di istruzioni può servire a
risolvere problemi diversi Parametri di una classe di problemi che vengono attualizzati in argomenti E.g., trovare la somma fra 314 e 512
Esecutore, Azioni, Processi� Ogni esecutore viene definito dalle azioni atomicheche può compiere� Anche dette azioni elementari� Processo� Azione composta da una sequenza di azioni elementari
(detti passi)� Programma (o procedura)� Descrizione di un processo (utilizzando un linguaggio comprensibile all’esecutore senza ambiguità)� Algoritmo� Procedura con certe caratteristiche (...vedi altri corsi...)
Macchine Astratte (1/2)� In generale, un esecutore ha a disposizione� Un organo di ingresso� Un organo di uscita� Una memoria (virtualmente illiminata) per memorizzare i risultati intermedi� Una procedura risolutiva (di un problema)� L’esecutore prototipo è una persona dotata
di carta e penna� La macchina di Turing nasce dall’osservazione del comportamento del matematico al lavoro
Modello di Von Neumann (3/3)� La procedura risolutiva può essere ripetuta� Un numero illimitato di volte� Anche per dati d’ingresso diversi� Tutti i calcolatori moderni sono macchine di Von Neumann
Hardware e Software� Hardware: oggetti fisici che compongono un calcolatore� Tipicamente elettronici� Tipicamente assemblati in un computer e in un
insieme di dispositivi periferici e di supporto� Software: insieme di procedure che guidano un calcolatore nell’attuazione delle proprie azioni elementari� Questo concetto si è profondamente evoluto da
Gerarchia di Macchine (1/2)� Un linguaggio L è un insieme di frasi ben formulate mediante simboli di un alfabeto A� Un linguaggio L è detto linguaggio di programmazione di una macchina M se M èun esecutore in grado di� Decidere se una frase è ben formulata� Eseguire le procedure (i programmi) scritti
Gerarchia di Macchine (2/2)� L’esecuzione di un programma scritto in linguaggio ��� è affidato ad una catena (arbitrariamente lunga) di macchine astratte che si reggono su una macchina concreta !� Ogni macchina è descritta completamente" Dal proprio linguaggio" Dalle proprie azioni
Interprete e Compilatore* Per realizzare una gerarchia di macchine, (ad ogni livello) abbiamo due possibilità+ Interprete, Esecuzione diretta degli ordini da parte della macchina
(gli ordini vengono trasformati in azioni)+ Compilatore, Traduzione ad un livello sottostante, Mediante un esecutore apposito (detto compilatore) che ha lo scopo di tradurre da un linguaggio - . ad un linguaggio - ./0
Interprete (1/3)* Macchina che esegue azioni a fronte di un programma scritto in un linguaggio * Equivale a fornire una caratterizzazione del significato (semantica operazionale) del linguaggio* Lega inscindibilmente la semantica di un linguaggio ad un esecutore specifico* Almeno un livello di interpretazione èsempre necessario
Interprete (2/3)1 I linguaggi interpretabili direttamente dai calcolatori elettronici sono molto lontani dal modo di ragionare di un risolutore umano2 Linguaggi a basso livello (di astrazione)1 È necessario disporre di linguaggi più simili al modo di ragionare dei risolutori umani2 Linguaggio ad alto livello (di astrazione)2 Il primo è stato il FORTRAN (FORmula
Interprete (3/3)3 Ogni macchina associata ad un linguaggio può essere descritta da una procedura che stabilisce la prossima istruzione da eseguire (e cosa eseguire)3 Un programma è costituito da un elenco di istruzioni, ciasuna delle quali appartenenti ad uno tra n possibili tipi di istruzioni I1, I2, ... ,In a cui corrispondono procedure da eseguire P1, P2, ... ,Pn
Compilatore (1/2)4 Un modo alternativo all’interpretazione per realizzare la semantica di un linguaggio L è quello di descriverne la traduzione in un linguaggio L’ di semantica nota4 Tipicamente L’ è il linguaggio di una macchina ad un livello più profondo nella gerarchia4 Identifica due fasi5 Compile-time: fase dedicata alla traduzione dal
programma P in 6 al programma semanticamente equivalente P’ in 6 75 Run-time: fase di esecuzione di P’ da parte di una macchina che interpreta 6 7
Compilatore (2/2)8 E.g., i programmi FORTRAN 9 Non possono essere interpretati da un calcolatore (degli anni ’50)9 Possiamo scrivere un traduttore che accetta (come dati) un qualsiasi programma FORTRAN e produce (come risultati) un programma per la macchina equivalente (in questo caso M0)8 Oggi, i compilatori sono dei programmi
molto soffisticati e potenti9 Il risultato della traduzione è spesso migliore (da qualche punto di vista) di un equivalente programma scritto direttamente in L0
Interprete vs Compilatore: Tipicamente; Il compile-time non viene considerato nella valutazione delle prestazioni di un programma; Il run-time di un programma compilato è molto inferiore a quello dell’equivalente interpretato< Almeno 10 volte (dato indicativo): I linguaggi di programmazione moderni sono troppo
complessi per essere interpretati; L’interpretazione di una piccola parte di programma richiede tempo per capire se la frase è ben formulata: Tipicamente, ci sono soluzioni intermedie; Linguaggi di scripting; Compilatori Just-in-Time
Livelli di Astrazione (1/3)= La gerarchia di macchine realizza una gerarchia di livelli d’astrazione> Più propriamente livelli di sistema= Ogni livello> Descrive il sistema di calcolo nel suo complesso> Fornisce un modello del sistema più vicino al
modo di pensare delle persone> Nasconde molti dettagli necessari ma poco interessanti
Livelli di Astrazione (2/3)? La macchina M0 è il calcolatore concreto (tipicamente elettronico)@ Interpreta gli ordini ed esegue azioni
(accende/spegne dei transistor)? Salendo nella gerarchia@ I dettagli dei livelli bassi vengono mascheratiA La memoria non è più limitata alla memoria centrale, ...@ Gli oggetti disponibili sono più complessiA Non solo numeri, anche vettori, matrici, testi, ...@ Le azioni elementari sono più complesseA Non solo aritmetica, anche manipolazione di testi, ...
Livelli di Astrazione (3/3)B Al livello di astrazione più alto, la macchinaC Capisce un linguaggio più simile a quello dell’uomoC Compie azioni complesse sul proprio mondoC È solo debolmente limitata dalle risorse disponibiliC ...B Il progetto Intelligenza Artificiale è il tentativo di realizzare la macchina al più alto livello di astrazioneC Ormai praticamente abbandonato in quanto taleC Le idee che ha introdotto nel tentativo di raggiungere il
risultato sono al centro di molta ricerca avanzata
InformazioneD Alcune domandeE Cos’è l’informazione?E Come si misura l’informazione?E L’informazione dipende da chi la trasmette? E da chi la riceve?E ...D Per capire queste cose abbiamo bisogno diE Concretizzare l’informazione in un messaggioE Trasmettere il messaggio verso qualcuno (o qualcosa) che lo interpretiE Misurare l’informazione acquisita della ricezione del messaggio
Alfabeto e Linguaggio (1/2)F Un insieme non vuoto e finito di simboli è un alfabetoG A = { a, b, c, ..., z }, A = { ♠, ♣, ♥, ♦, ..., ☻ }, ...F Dato un alfabeto A, A* è l’insieme delle sequenze finite generabili con i simboli di AG Le sequenze vengo dette stringheG Non poniamo limite alla lunghezza delle stringheG La stringa vuota ε∈A*F Un linguaggio L su un alfabeto A è un sottoinsieme di A*
Alfabeto e Linguaggio (2/2)F Un linguaggio L può essere definitoG In modo estensionale, cioè per enumerazionedei suoi elementiH Sempre finito in questo casoG In modo intensionaleH Mediante una serie di regole d’appartenenza, che
prendono il nome di grammaticaF Detta S∈L una stringa, è possibile definireG |S|, la lunghezza della stringaG Per ogni G∈L, S○G, la stringa ottenuta dalla concatenazione di S e GH Anche se S∈I e G∈I, non è garantito che SJG∈I
Trasmissione dei SimboliK Trasmettitore (sorgente) di simboliL Rappresenta l’informazione che vuole inviare nei termini di una stringa di simboli da trasmettereK Ricevitore (destinazione) di simboliL Interpreta l’informazione partendo dalla stringa di simboli ricevuta
Canale trasmissivo (ideale o rumoroso)simbolo s simbolo s’
Simboli e InformazioneM Le stringhe rappresentano l’informazioneN Danno concretezza ad un’astrazioneM Le stringhe possono essere codificate in forme diverseN Alfabeti diversiN Grammatiche diverse per il linguaggioN ...M In generale, esistono codifiche diverse per scopi diversiN MemorizzazioneN Elaborazione (manipolazione di stringhe)N ...
Misura dell’Informazione (1/2)O L’informazione I(a) portata da un simbolo a∈A èlegata a P{x’=a}P Probabilità di ricevere il simbolo aO Vediamo due casi particolamente interessantiP P{x’=a} è grande (Q1), l’informazione portata dal simbolo è
piccolaP P{x’=a} è piccola (R0), l’informazione portata dal simbolo ègrandeO Per comodità, richiediamo che l’informazione
associata ad un simbolo a sia una quantità positivaed additiva (definizione di Shannon)P I(a) = -log2 P{x’=a} (l’unità di misura è il bit)
Misura dell’Informazione (2/2)O Misurare l’informazione consente diP Misurare la ridondanza di un messaggioS Come posso ridurre la lunghezza della stringa trasmessa?P Misurare la perdita d’informazione nella trasmissioneS Quando veloce posso trasmettere accettando un certo errore?P Misurare la perdita di informazione nella codifica (o nella
transcodifica)S Quale parte della stringa trasmessa posso tralasciare accettando un certo errore?P Studiare codifiche migliori per scopi diversiP ...
Codifica Binaria (1/3)T Dato un alfabeto finito A, ogni stringa di A* può essere codificata in una stringa (tipicamente più lunga) di simboli presi da un alfabeto B di due soli simboliU Di solito, B = { 0, 1 }T In codifica binaria, i simboli vengono detti bit(binary digit)T EsempioU A = { a, b, c, d } U a→00, b→01, c→10, d→11U S = abbccdd→S = 00010110101111
Codifica Binaria (2/3)T In generale, da un alfabeto di m simboli èpossibile generare mn stringhe diverse di lunghezza nT Codifica binaria a lunghezza costanterichiede un numero di bit n pari a
2n = |A| n = log2|A|T Quindi, detta SV una stringa ed SW la sua transcodifica binaria a lunghezza costante
Codifica Binaria (3/3)X Quando si parla di lunghezza di stringhe binarie si usano i dei prefissiX Approssimazioni con potenze di 2 di quelli usati comunemente in fisica, chimica, ...X Spesso si parla in termini di byte, blocchi di 8 bitY Nibble (o nybble), 4 bit ≈1015250
Rappresentazione dei Naturali (1/3)Z L’insieme N dei numeri naturali è infinito[ N = { 0, 1, 2, ... }[ Altri corsi parlano di come si costruisce questo insiemeZ Serve una grammatica per rappresentare
ogni numero con una stringa di simboli[ Una rappresentazione estensionale non bastaZ Civiltà diverse hanno adottato grammatiche diverse[ Numeri romani[ Oggi, in occidente, si utilizzano i numeri arabi
Rappresentazione dei Naturali (3/3)] E.g., b=2^ S=11001, n=25^ n=19, S=10011] E.g., b=8^ S=57, n=47^ n=52, S=64] E.g., b=16 (usiamo delle lettere per completare l’alfabeto)^ S=F5, n=245^ n=19, S=13] Per evitare ambiguità, indichiamo la base nel pedice del numero: n=1910=1316=000100112
Rappresentazione dei Reali (1/2)_ L’insieme R è continuo e non può essere rappresentato tutto` Alfabeto finito` Stringhe illimitate (ma non infinite)_ Vari sottoinsiemi di R possono essere rappresentati` Numeri relativi (Z)a Estendiamo l’alfabeto con { +, - } e modifichiamo la
grammatica` Numeri razionali (Q)a Estendiamo l’alfabeto con { . } e modifichiamo la grammatica
Rappresentazione dei Reali (2/2)a E.g., b=2b S=-11001, n=-25b n=19.375, S=10011.011a E.g., b=8b S=-57, n=-47b n=52.25, S=64.2a E.g., b=16 (usiamo delle lettere per completare l’alfabeto)b S=-F5, n=-245b n=19.625, S=13.Aa Attenzione: questa notazione non è praticamente utile per realizzare un calcolatoreb In realtà (come vedremo) se ne usano altre
Codifica dei Testi (1/4)c Un testo è una sequenza di caratteric Un carattere può essere d Una lettera d Un numerod Un simbolo speciale (punteggiatura, ...)c Codifichiamo il testo un carattere alla voltad Anche se una codifica per parole potrebbe essere utilizzata
Codifica dei Testi (2/4)e La codifica ASCIIf American Standard Code for Information Interchangef Introdotta per definire uno standard per l’input/output da/verso terminalif Sviluppata negli USAe Comprende 127 caratterif 7 bit in codifica binariaf L’ottavo bit è di verifica (parity bit)f Comprendeg Caratteri stampabilig Caratteri di controllo (a
Codifica dei Testi (3/4)h ASCII è stato esteso utilizzando l’ottavo bit per caratteri non-USAi Lettere accentate, caratteri grafici, ...h Recentemente Unicode estende ASCIIi Un unico formato per tutte le linguei Formati a lunghezza fissa o variabile (in base al valore
dell’ottavo o del sedicesimo bit)i Vari UTF (Unicode Transformation Format)h Nella pratica programmativai IETF (Internet Engineering Task Force) richiede UTF-8 (lunghezza variabile fino a 32 bit)i Java e Microsoft Windows (NT o superiore) usano UTF-16 (almeno 16 bit, lunghezza variabile)
Rappresentazione dei Suonij Un suono è un fenomeno fisico continuok Pressione dell’aria sulla membrana del microfonok Tensione elettrica a valle del microfonoj Per trattare un suono è spesso necessario
digitalizzarlok Campionamento, il suono viene misurato solo in alcuni istanti di tempok Quantizzazione, il valore di ogni campione viene discretizzato e limitato in un intervallo
Codifica dei Suonin Diversi valori forniscono diverse qualità di digitalizzazioneo CD, fc=44.1 kHz, l=216 (16 bit), stereoo Telefono, fc=8 kHz, l=28 (8 bit), monon La qualità può essere sinteticamente misurata con la bit-rate b=fckn, con l=2k e nnumero di canalio CD, q=172.2 Kbyte/so Telefono, q=7.8 Kbyte/sn Per una canzone di 4 minuti in un CD servono circa 41.3 Mbyte
Codifica delle Immaginin Le immagini vengono digitalizzate in pixel(picture elements)o Campionamento in base alla risoluzione rp Fotocamera economica: r=2272x1704 (≈4Mpixel)p Tipicamente in rapporto 4/3 o 16/9o Quantizzazione su 24 bitp 8 per ognuno dei 3 canali R (red), G (green) e B (blue)n Per una fotografia digitale servono circa 11 Mbyte
Codifiche dei Videoq Campionamento nello spazio e nel tempor Ogni fotogramma è codificato come un’immaginer 24/30 fotogrammi al secondo per il cinemaq La bit rate di un video di qualità (e.g.,
1280×720) a 24 fotogrammi al secondo ècirca b=63.2 Mbyte/sr Quindi, per memorizzare un ora di video
Codifiche Ridondanti (1/2)q Spesso, i linguaggi impongogno delle regole grammaticali per cui i messaggi risultano ridondantir Un messaggio è ridondante se richiede “più
simboli del necessario”q Esempior Tipcamnte le parole lnghe contngno parcchi cartteri che potrbbro essre elimnatir Seocndo uno stiduo di una Univretisà Inlegse l’oridne dlele letetre all’intreno di una praola non è improtatne, ciò che improta è la pirma e l’utlima letetra
Codifiche Ridondanti (2/2)s In caso di linguaggi ridondanti, abbiamo due possibilitàt Codificare in un altro linguaggio togliendo la
ridondanzau Tipicamente, si ottengono messaggi più previt Sfruttare la ridondanza per altri altri scopiu Forward Error Detection, scoprire eventuali errori (di trasmissione o di memorizzazione)u Forward Error Correction, correggere eventuali errori (di trasmissione o di memorizzazione)
Codifica di Hammingu Usato principalmente per individuare errori su singoli bitv È anche possibile la
correzione aumentando la ridondanzau Codifica delle cifre da 0 a 9
utilizzando 5 bit (anziché 4)v Si associa ad ogni cifra una stringa binaria in cui sono presenti sempre due 1 e tre 0 (o viceversa)v In caso di errore, la stringa potrebbe assumere una delle altre 22 configurazioni 00011 9
Codifica di Huffman (1/10)w Codifica binaria a lunghezza variabilew Simboli più probabili (più frequenti) vengono codificati con stringhe più cortew È alla base del formato ZIPx Massimo rapporto di compressione (lunghezza
finale / lunghezza iniziale)x Deve considerare l’intera stringa da codificarey Operazione di codifica lentax Non sfrutta le “caratteristiche fisiologiche” delle stringhey Non sfrutta in nessun modo l’uso finale delle stringhe
z Per la costruzione del codice si parte dalle probabilità dei singoli simboli{ Approssimata con la relativa frequenzaz Passo 1: si costruisce un nodo foglia per ogni lettera, etichettandolo con la frequenza del simbolo
Codifiche Lossy~ Una codifica è lossless se è possibile ricostruire la stringa iniziale senza errori~ Le codifiche lossy � Ammettono che la stringa ricostruita abbia
qualche errore� Utili nel caso in cui l’informazione possa comunque essere preservata� Tipicamente usate quando il destinatario è una persona� Suoni, immagini, video, ...
Codificha JPEG (1/2)~ Codifica lossy per immagini~ Si basa su una codifica a blocchi 8x8 dell’immagine~ Ogni blocco è codificato separatamente dall’altro~ Viene tenuto conto anche della sensibilitàdell’occhio umano agli errori introdotti nella quantizzazione~ Si possono ottenere elevati fattori di compressione
Codifica MPEG� Lo standard più diffuso nel settore della codifica audio e video è lo standard MPEG (Motion Picture Expert Group)� Nato per codificare video e il relativo audio con
qualità VHS su supporto CD� Vari standard con varie prestazioni� MPEG-1, comunemente usato per l’audio (il livello 3 viene detto comunemente MP3)� MPEG-2, comunemente usato nei DVD� MPEG-4, pensato per il Web
Rappresentazione Posizionale� Dato un alfabeto A di b simboli, ord(.) è un ordinamento totale su A in [0, b-1]� A = { a, b, c, d } � ord(a) = 0, ord(b) = 1, ord(c) = 2, ord(d) = 3� Dato un alfabeto A di b simboli
S = dn-1 dn-2 ... d1 d0 .d-1 d-2 ... d1-m d-mval(S) = Σiord(di)bi (≥0)� Fissata la base, la rappresentazione
posizionale è unica� A meno di zero inziali, varianti di ord, ...
Conversione tra Basi� Dato un intero x in base b, trovare la sua rappresentazione in base b’� Se b o b’ valgono 10� Possiamo usare le comuni regole dell’aritmetica� Che non padroneggiamo bene per basi diverse da 10� Separiamo i casi di parte intera e parte
frazionaria� Attenziona: la conversione della parte frazionaria può non terminare� Passando dalla base 10 è possibile fare una
Conversione tra b e bk� Se b’=bk (k>1) possiamo fattorizzare il polinomio usato nella rappresentazione posizionale in modo conveniente� Separiamo la stringa S in gruppi di k simboli e poi convertiamo i singoli gruppi� Aggiungiamo 0 non significativi se serve� Utile per le conversioni� Binario/ottale (b=2, b’=8)� Binario/esadecimale (b=2, b’=16)
Aritmetica in base b� Estendiamo le operazioni di somma e prodotto ad una base b qualsiasi� Per la base 10� Somma� Una cifra per volta, eventuale riporto di 1� Prodotto� Ridotto a prodotto per cifra singola� Eventuale riporto di 8� Basta trovare le “tabelline” per la base b
Somma e Prodotto in Base 2� Operazioni molto semplici� Necessari molti passaggi� Un solo caso di riporto� Il prodotto si riduce a “copia e somma”� Realizzazione elettronica semplice
Numeri Interi nei Calcolatori (1/2)� In un calcolatore la quantità di memoria dedicata ad un singolo numero è fissata (detta parola)� 8, 16, 32, 64, ... bit� Si possono rappresentare numeri con una quantità fissa di cifre � Numeri a precisione finita
Numeri Interi nei Calcolatori (2/2)� Fissata una base b ed una lunghezza N, i naturali rappresentabili sono in [0...bN-1]� In binario, con parole di 8 bit, [0...255]� Se il risultato di un’operazione eccede il limite� Il risultato viene troncato a N simboli� Si parla di overflow
Numeri Binari Negativi� Il modo più semplice è sacrificare il primo bit� Il bit di segno contiene l’informazione + (0) o -(1)� Rappresentazione modulo/segno� Con N bit, [-2N-1-1...2N-1-1]� Utilizzata in passato, ma ormai quasi del
tutto abbandonata� Lo 0 ha due rappresentazioni� Il tipo di operazione dipende anche dal segno dei termini� A+B è una sottrazione se A e B hanno segno discorde
Complemento a 2 (1/3)� Per rappresentare k in una parola di N bit� Se k≥0, si usa il modulo/segno� Se k<0, si usa il modulo/segno con segno a 1 e modulo pari a (2N-1-|k|)� E.g., su 5 bit� +1410=011102� -1410=100102
Complemento a 2 (2/3)� In complemento a 2, il bit più significativo ha peso 2N-1� Se 0 non da contributo� Se 1 il valore è (2N-1-y) con y valore dei bit meno
significativi (y=2N-1-|k|)� Quindi, in complemento a 2 a N bit èpossibile rappresentare i numeri in
Complemento a 2 (3/3)� Alcune proprietà interessanti� 0 si rappresenta con 000...00� -1 si rappresenta con 111...11� Il massimo numero positivo è 011..11� Il minimo numero negativo è 100...00� Dato un numero negativo, scambiando 0 e 1 (operazione di complemento) si ottiene il suo modulo diminuito di 1� E.g., su 4 bit -510=10112→01002=410
Conversione Veloce (1/2)� Dato un numero negativo -A (A>0) per trovare velocemente la sua rappresentazione con N bit � Si rappresenta A sugli N bit� Si scambiano 0 con 1� Si aggiunge 1� E.g., -1810 su 6 bit� 1810=0100102→1011012 →1011102=-1810
Conversione Veloce (2/2)� Riunendo gli ultimi due passi, dato un numero negativo -A (A>0) per trovare velocemente la sua rappresentazione su Nbit � Si rappresenta A su N bit� Si complementano tutti i bit a sinistra dell’1
meno significativo� E.g., -1810 su 6 bit� 1810=0100102→1011102=-1810
Operazioni in Complemento a 2� Il cambiamento di segno si ottiene complementando tutti i bit a sinistra dell’1 meno significativo� È il secondo passo della regola di conversione
veloce� Dati due numeri in complemento a 2 su Nbit, la loro somma troncata su N bit è il complemento a 2 del risultato della somma� Sfruttiamo questo anche per la differenza, infatti
Somma in Complemento a 2� E.g., su 5 bit (senza errore)� 710-510=(00111)2+(11011)2=1000102=210� -510-110=(11011)2+(11111)2=1110102=-610� E.g., su 5 bit (con errore di overflow)� 910+910=(01001)2+(01001)2=100102=-1410� -910-810=(100111)2+(11000)2=1011112=-1710� C’è errore di overflow se e solo se i due addenti sono dello stesso segno ed il risultato è di segno opposto
Rappresentazioni Meno Comuni� La rappresentazione degli interi più comune è quella in complemento a 2� Modulo/segno è ormai abbandonato� Complemento a 1� I numeri negativi si ottengono dal loro modulo
mediante complemento -510 su 5 bit è 110102, infatti 110102→001012� Eccesso 2N-1 (per N bit)� Il numero è trattato come positivo e poi si sottrae (sempre) 2N-1-1 -510 su 5 bit è 010102, infatti 010102=10=5-15
Rappresentazione dei Reali¡ In una stessa applicazione è spesso necessario rappresentare numeri¢ Interi e non interi¢ Molto grandi¢ Molto piccoli¡ Fissata la lunghezza della parola, è difficile rappresentare numeri di ordini di grandezza diversi¢ Rappresentazione in virgola fissa¢ Rappresentazione in virgola mobile
Rappresentazione con Virgola Fissa¡ Fissato N la lunghezza della parola ¢ Il bit più significativo indica il segno¢ Ni bit rappresentano la parte intera¢ Nf bit rappresentano la parte frazionaria (con pesi positivi, come fossero interi)¡ I valori Ni, Nf (N = 1 + Ni + Nf) sono fissati a
priori¢ Da cui nome virgola fissa¢ Ovviamente non tutti i numeri reali sono rappresentabili
Rappresentazione con Virgola Mobile (1/4)£ La rappresentazione in virgola mobile (floating point) sfrutta la notazione scientifica dei numeri¤ E.g., 7100000=7.1 106£ Fissata una base b, un numero k èdescritto da <m,e> con k=mbe¤ Mantissa m¤ Esponente e
Rappresentazione con Virgola Mobile (2/4)¥ Nota¦ La scelta di <m,e> è non univoca se non si aggiungono regole sulla scelta di m¦ È importante non confondere b con la base usata per la rappresentazione§ Anche se spesso sono uguali¥ Tipicamente, si sceglie m (≠0) in modo che
m=±0.d1d2... con d1≠0¦ Con questa convenzione, la rappresentazione èunivoca (forma normale, con convenzioni per 0)¦ b-1≤|m|<1
Standard IEEE 754 (1/4) Ogni produttore aveva un suo formato® Fine anni ’70 la IEEE (Institute of Electrical and Electronics Engineers) costituisce un comitato per standardizzare la rappresentazione floating-point® Tre formati¯ Singola precisione (32 bit)¯ Doppia precisione (64 bit) ¯ Precisione estesa (80 bit) Nel formato IEEE 754 viene scelta® Base 2 per mantissa® Notazione in eccesso per l’esponente® Mantissa normalizzata (tipo 1.x)
° IEEE 754 prevede numeri normalizzati e denormalizzati° Formati speciali per identificare ± Infinito ± NaN (Not a Number, e.g., se dividiamo infinito per infinito)
Algebra (Binaria) di Boole² Detto B={0, 1}, studia le funzioni f:BN→BM³ Introdotta da George Boole per studiare la logica (proposizionale) ed una teoria degli insiemi³ Spesso, si usano B={false, true}, B={falso, vero}, B={f, t}, B={f, v}, ...² Nota³ Una funzione f:BN→BM può sempre essere espressa come M funzioni f:BN→B (spesso dette funzioni Booleane)³ Essendo |B|, N, M finiti, il numero di possibili f èfinito (per M=1, sono 2K, K=2N)
Espressioni Booleane (1/3)¶ Tre operazioni sono tipicamente usate per esprimere le funzioni Booleane· NOT (-), negazione, unaria¸ Complementa il suo argomento· AND (·), congiunzione, binaria¸ Vale 1 solo se i due argomenti valgono 1· OR (+), disgiunzione, binaria¸ Vale 0 solo se i due argomenti valgono 0¶ Le operazioni si comportano · Come quelle note dall’aritmetica (circa) · Come quelle della teoria degli insiemi
Espressioni Booleane (2/3)¹ Spesso viene introdotto ancheº XOR (⊕), OR esclusivo, binario» XY+XY¹ Tavole di verità dei connettiviº In termini insiemistici: complemento, unione, intersezione, differenza simmetrica
Forme Canoniche SP e PS (1/2)¼ Data una qualsiasi funzione Booleana è sempre possibile esprimerla come½ Somma di Prodotti (tra variabili e relativi complementi)½ Prodotti di Somme (tra variabili e relativi complementi)¼ Entrambe le forme non sono univoche½ Problema di minimizzare il numero di prodotti e di somme½ Spesso si usano anche forme non minime perché più
semplici da realizzare¼ Si dicono canoniche se, mediante l’aggiunta di convenzioni, vengono rese univoche½ Per ogni funzione Booleana esiste ed è unica la sua forma
Forme Canoniche SP e PS (2/2)¼ Data una tavola di verità è semplice trovare le forme SP e PS equivalenti¼ E.g., funzione di maggioranza½ 1 se il numero di 1
supera il numero di 0½ ABC+ABC+ABC+ABC½ (A+B+C)(A+B+C) (A+B+C)(A+B+C) 1111
Operazioni NAND e NOR¾ Per sintetizzare una qualsiasi funzione Booleana èsufficiente un solo connettivo (tra)¿ NAND, X NAND Y=(XY)¿ NOR, X NOR Y=(X+Y)¾ In generale, il numero di NAND/NOR è maggiore del numero di operatori NOT/AND/OR¿ X = X NAND X
= X NOR X¿ XY = (X NAND Y) NAND (X NAND Y)= (X NOR X) NOR (Y NOR Y)¿ X+Y = (X NAND X) NAND (Y NAND Y)= (X NOR Y) NOR (X NOR Y)
Sommatore Binario (1/2)À Si consideri il problema di sintetizzare una funzione che sommi tre cifre binarie a, b, c generando anche il riporto rÁ s = abc+abc+abc+abcÁ r = ab+bc+acÀ Questo è un “modulo” che può essere utilizzato per realizzare un sommatore binario ad N bit
Reti Logiche CombinatorieÄ L’elettronica implementa le funzioni BooleaneÅ Reti logiche combinatorieÄ Servono componenti a due stati per rappresentare le variabili BooleaneÄ Lo stato degli interruttoricontrolla lo stato delle lampadineÄ Sono un insieme funzionalmente completoÅ Implementano i tre
TransistorÆ Componente che realizza un interruttore controllato da un segnale elettricoÆ Lo stato dell’interruttore Ç Non viene impostato con un operazione
meccanica manualeÇ Viene impostato mediante un segnale elettricoÆ Varie tecnologie realizzano diversi tipi di transistorÇ I più usati sono i transistor (ad effetto di campo)
Transistor NMOS e PMOS (2/3)È I segnali logici sono realizzati fissando la tensione ai tre morsetti del transistorÉ 0, tensione di massa (0V)É 1, tensione di alimentazione (tipicamente 5V)È La corrente fluisce da drain verso sourceÈ I tue tipi di transistor sono complementariÉ Si aprono/chiudono per tensioni opposteÉ Da cui il nome di tecnologia Complementary
Circuiti IntegratiË Circuiti complessi realizzati su uno stesso chipË Diversi livelli di integrazioneÌ SSI, Small Scale Integrated (<50 transistor)Ì MSI, Medium Scale Integrated (< 500 transistor)Ì LSI, Large Scale Integrated
(<500k transistor)Ì VLSI, Very Large Scale Integrated (>500k transistor)
Porte LogicheÍ Componenti fondamentali (atomici) dei circuiti digitaliÍ Ricevono in input un insieme di segnali elettrici (logici) e generano in output un segnale elettrico (logico)Î Sono implementati mediante transistor
Famiglia LogicaÏ Insieme funzionalmente completo di porte logiche tra loro compatibiliÐ Collegabili liberamenteÏ Corrispondenza 1 a 1 tra espressioni Booleane e reti combinatorieÐ f = ab + bc
Implementazione di una FunzioneÑ Una rete combinatoria implementa una funzione Booleana fÒ Si individua la specifica funzionale di f nei
termini di una tavola di verità o di una espressioneÒ Si cerca un’espressione equivalenteÒ Si minimizza l’espressione tenendo contoÓ Della tecnologia (famiglia logica, vincoli elettrici, ...)Ó Di un criterio di ottimizzazioneÒ Si sintetizza la rete combinatoria
ROMÔ ROM (Read-Only Memory) è una particolare rete combinatoria con N ingressi ed M usciteÕ Gli ingressi formano un indirizzoÖ Di solito viene letto come un numero naturaleÕ L’uscita è il valore associato
all’indirizzoÔ Una ROM implementa una qualsiasi tabella di veritàÕ Funzione f:×N→ ×MÕ Spesso detta Look-Up
PLA (2/2)Ø L’uso di PLA (di ROM in generale) ha dei vantaggiÙ Sistematicità del progettoÙ Flessibilità e completezzaÚ Basta cambiare (o riprogrammare) la ROMÙ AffidabilitàØ Svantaggi maggiori sonoÙ Impossibilità di ottimizzare il circuitoÙ Impossibilità di realizzare circuiti complessi
Altri tipi di ROMÛ PROM (Programmable ROM)Ü Una sola volta, non in fabbricaÛ EPROM (Erasable PROM)Ü Cancellabili medialte esposizione alla luce ultraviolettaÛ EEPROM (Electrically Erasable PROM)Ü Cancellabili per mezzo di impulsi elettrici Ü Molto lente rispetto alle precedentiÛ FLASH (a causa l’alta velocità)Ü EEPROM cancellabili a blocchiÜ Oggi, hanno velocità ed affidabilità paragonabile a quella dei dischi rigidi
ß Più semplice dei circuiti aritmeticiß Dati N bit di input, l’output è ottenuto spostando di 1 bit la stringa di inputà La direzione dello spostamento dipende da Cà È aritmetico perché viene riempito l’output con uno 0à Equivale a moltiplicare/dividere per 2
De-/Multiplexer (1/4)á Un multiplexer (MUX) ha 2N input, 1 output e N input di controlloá Le linee di controllo determinano quale dei 2N input viene inviato all’outputá Un demultiplexer (DEMUX) invia il segnale di input ad uno dei 2N output, a seconda dei valori delle N linee di controllo
De-/Multiplexer (4/4)â Un MUX è formato da un decoder piùã AND tra ogni Di e la
relativa linea del decoderã OR che produce l’uscitaâ Un MUX con N input di controllo può implementare qualsiasi f funzione Booleana N-ariaã I valori degli N input
selezionano un Di che viene tenuto fisso al valore dell’uscita dell’i-esima riga della tabella di verità di f
ALUä Arithmetic Logic Unit (ALU) è una rete combinatoria che compie operazioni aritmetiche e logicheå Operazione da eseguire sull’input (M bit)å Dati di input da elaborare (N bit)å Flag che modificano il comportamento dell’operazioneæ Somma 1 al risultato, cambia di segno il risultato, ...å Output dell’elaborazione (N bit o 2N bit)å Flag che indicano situazioni particolariæ Overflow, il risultato è 0, il risultato è negativo, ...ä La caratteristica più importante è che il suo comportamento dipende dai bit che codificano l’operazione
ALU ad 1 bitç Esegue NOT, AND, OR e somma ad 1 bitç F sceglie l’operazioneç ENA e ENB (linee di enable) abilitano la lettura di Aè 0 altrimentiç INVA sceglie se usare A o NOT Aç Di norma INVA = 0, ENA = ENAB = 1
ALU ad 8 bit (2/2)é Ottenuta mettendo in cascata più ALU ad 1 bitê Può essere messa in cascata con altre ALU ad 8 bité Il carry-in può essere usato come flag INCê Flag sull’operazione per fare A+1 o A+B+1 in un solo calcolo (se INC=1)é È semplice ottenere due flag di uscita molto comuniê N, il valore del risultato è negativo (bit più significativo del risultato)ê Z, il valore del risultato è 0 (NOR dei bit in uscita)
Automi a Stati Finiti (1/2)ë Macchina (o automa o agente o ...)ì Dispositivo automatico in grado di interagire con l’ambiente esterno ì Esibisce un comportamento (in uscita, output) a fronte di uno stimolo (in ingresso, input)ë Interessiamoci di macchine con memoria
finitaì Per macchine più potenti ammettiamo memoria illimitata (ottenendo così le macchine più potenti, le Macchine di Turing)
Automi a Stati Finiti (2/2)ë FSM, Finite State Machineë Vista come una scatola nera, descriviamo cosa succede ad ogni passoì Legge un simbolo in ingressoí Che appartiene ad un insieme finito Aì Produce un simbolo in uscitaí Che appartiene ad un insieme finito Bì Cambia il proprio stato interno í La memoria è finitaí L’insieme Q degli
FSM Distributore di Biglietti (1/4)î Un distributore di bigliettiï Accetta solo monete grandi (MG) e monete piccole (MP)ï Un biglietto viene emesso quando vengono ricevute una MP ed una MG ð Non importa l’ordine di immissione delle moneteï Non viene dato resto, è necessario sempre introdurre MP e MGï Non vengono restituite le monete se non si procede all’acquisto
FSM Distributore di Biglietti (2/4)î L’insieme (finito) dei simboli di ingresso èA={MP, MG}î L’insieme (finito) dei simboli di uscita èB={ancora, restituisci, emetti}î L’insieme (finito) degli stati è Q formato daï q0, non è stata inserita nessuna mometaï q1, è stata inserita una MPï q2, è stata inserita una MG
Automa a Stati Finiti di Mealyñ Un automa a stati finiti di Mealy M è una quintuplaM = <A, B, Q, o, s>
A insieme finito di simboli di ingressoB insieme finito di simboli di uscitaQ insieme finito di simboli di statoo:AxQ→B funzione di uscitas:AxQ→Q funzione di cambiamento di statoñ Esistono altre definizioni, a seconda dell’uso che si intende fare dell’automaò Riconoscitore/generatore di linguaggi, ...
Implementazione degli FSMõ Una volta scelta la codifica (binaria) degli elementi di A, B e Q, le funzioni o ed s sono implementabili con reti combinatorieõ Serve un modo perö Memorizzare lo stato corrente (quando serve)÷ Le reti combinatorie non hanno memoriaö Sostituire lo stato corrente con lo stato futuro
Reti Logiche Sequenziali (1/3)ø Le FSM sono implementate da reti logiche sequenzialiù Le funzioni o e s sono realizzate da reti logiche
combinatorieø Problemi apertiù Serve un modo per stabilire quando lo stato futuro prende il posto dello stato correnteù Ci serve memorizzare lo stato? Se sì, come?
Reti Logiche Sequenziali (2/3)ú Reti logiche sequenziali asincroneú L’ouput di s viene richiuso sull’input di s e di oú Lo stato non viene memorizzatoú Lo stato futuro prende il posto dello stato corrente appena quest’ultimo cambiaû A meno del ritardo dovuto
alla propagazione dei segnali elettriciú Difficili (ma non impossibili) da
progettare perché viene richiesto un comportamento deterministico e ripetibile
Reti Logiche Sequenziali (3/3)ý Reti logiche sequenziali sincroneý L’ouput di s viene campionatoþ Dal fronte di salita di cý Lo stato viene memorizzato e cambia solo negli istanti di campionamentoý All’istante di campionamento lo stato futuro prende il posto dello stato correnteþ A meno del ritardo dovuto
Clock (1/3)ÿ Nel caso della FSM Distributore di Biglietti, il comando di campionamento viene dato all’immissione di una moneta� Nel momento in cui viene rilevata la moneta, viene
generato un breve segnale elettrico (impulso)ÿ Tipicamente, il comando di campionamento èperiodico � In questo caso viene detto clock� Periodo di clock: periodo di tempo minimo tra due
attivazioni successive (misurato in frazioni di secondo)� Frequenza di clock: inverso del periodo di clock (misurato in multipli di Hz)
Clock (2/3)� La frequenza di clock deve essere tale da assicurare che le reti logiche combinatorie siano stabili prima del prossimo campionamento� Tipicamente, sufficientemente bassa da poter
trascurare i ritardi dovuti alla propagazione elettrica� Spesso il segnale di clock viene generato
da un oscillatore al quarzo� Frequenza molto stabile ed elevata� Economicità, robustezza ed affidabilità
Registro ad 1 bit (1/3)� Nell’implementazione delle reti logiche sequenziali sincrone rimane un problema� Come realizzare il registro che contiene lo
stato?� Non possiamo appoggiarci ad un’altra rete logica sequenziale sincrona� Registro ad 1 bit (latch ad 1 bit)� Due ingressi i e β ed un uscita o� Mantiene uno stato interno s� Se
Segnale Impulsivo (1/2) Il segnale β viene posto a 1 per il tempo necessario a far propagare il valore di i su o� L’uscita di un registro rimane insensibile alle
variazioni dell’ingresso se β=0� Il ritardo ∆ e la breve durata di β garantiscono che non si generi un’oscillazione nel circuito Il segnale β viene detto impulso� Se è periodico è simile ad un clock� Il registro è sensibile ai valori di β, non ai suoi fronti di salita
Latch e Flip-Flop (1/3)� Un latch è azionato dal livello (tipicamente 1)� È level triggered� Un flip-flop è azionato dal fronte (tipicamente di salita)� È edge triggered� La lunghezza dell’impulso di clock non è importante� Insensibile alle variazioni dei segnali tranne negli istanti di
campionamento� Per utilizzare il latch D come fosse un FF serve un piccolo circuito che sia sensibile ai fronti di clock� Che mantenga lo stato 1 per breve tempo in modo che D
possa essere considerato costante in quel periodo di tempo
(a) latch di tipo D attivato con livello 1 del clock(b) latch di tipo D attivato con livello 0 del clock(c) flip-flop di tipo D attivato dal fronte di salita del clock(d) flip-flop di tipo D attivato dal fronte di discesa del
Bus Interno (1/3)� Componente di trasferimento dati tra registri ad N bit all’interno di un chip� 2l registri sorgente� 2k registri destinazione� Un unica linea di clock� È necessario individuare � 1 tra gli 2l registri
Bus Interno (3/3)� La selezione del registro sorgente avviene mediante un MUX a l ingressi di controllo� La selezione del registro destinazione avviene mediante un DEMUX con kingressi� Le uscite a 0 mascherano il segnale di
Tipi di Bus� Il bus interno trasferisce dati tra componenti di uno stesso chip� Singolo clock (a frequenza massima)� Ridotta potenza� Per collegare un chip con l’esterno si usano vari bus esterni� Per collegare una CPU alla memoria
centrale (attualmente con clock intorno ai 400MHz)� Per collegare una CPU ai dispositivi di I/O (attualmente con clock: PCI, 33MHz, ISA 8.33MHz)� Elevata potenza (ridotta velocità)� Necessitano di un controllo decentralizzato (arbitraggio)
Memoria� Una memoria è un dispositivo che permette di leggere/scrivere dati(di larghezza fissa) in base ad un indirizzo� Una volta scritti, i dati permangono e possono essere letti in futuro
Caratteristiche di una Memoria (1/2)� Dimensione della cella� Numero di bit a cui è associato un certo indirizzo� Numero di celle� Numero di diversi indirizzi che la memoria contiene� Capacità� Numero di bit complessivamente contenuti nella memoria (tipicamente misurato in multipli di byte)� Parallelismo in scrittura/lettura� Numero massimo di celle che possono essere scritte/lette contemporaneamente� Velocità di accesso in scrittura/lettura
Caratteristiche di una Memoria (2/2) ROM (Read-Only Memory)! Può essere scritta una volta sola! Ha molte varianti (PROM, EPROM, ...) RAM (Random-Access Memory)! Il tempo richiesto per l’accesso è (circa) indipendente dall’indirizzo Volatili (o non volatili)! Mantengono i dati solo quando sono alimentate Rimuovibili (o non rimuovibili)! È possibile sostituirle durante l’operatività del sistema Dicendo RAM si intende (quasi sempre) una tra! Memoria ad accesso casuale, volatile, a semiconduttore! Memoria scrivibile liberamente
Memoria a Semiconduttore (1/3)" Molte categorie di supporti sono memorie a tutti gli effetti# CD, DVD, nastri, ..." Le memorie a semiconduttore sono tipicamente veloci, poco capienti, volatili, non rimuovibili" Le memorie a semiconduttore vengono# Realizzate in chip detti chip di memoria# Integrate nello stesso chip dove risiedono la ALU ed altri
componenti (memoria cache)" In ogni calcolatore c’è sempre almeno una memoria a semiconduttore detta memoria centrale# Oggi tipicamente compresa tra 0.5 Gbyte e 10 Gbyte
Memoria a Semiconduttore (2/3)$ Memoria 4 x 3$ 8 linee di input% 3 per i dati di input% 2 per l’indirizzo% 3 per i bit di controllo% 3 per output$ Bit di controllo% Chip Select (CS)% Read (RD) per distingure tra read e write% Output Enabled (OE) per abilitare l’output
Memoria a Semiconduttore (3/3)& Scrittura' Il dato entra nelle linee I' L’indirizzo entra nelle linee A( Il DEMUX sceglie la riga da abilitare( CS·RD abilitano la scrittura sulla riga& Lettura' L’indirizzo entra nelle linee A( Il DEMUX sceglie la riga da abilitare( CS·RD abilitano la lettura sulla riga( CS·RD·OE abilitano le linee di uscita' Il dato esce dalle linee O& L’ultimo stadio su O è l’uscita
RAM a Semiconduttore) SRAM (Static RAM)* Realizzate mediante FF-D* Estremamente veloci) DRAM (Dynamic RAM)* Realizzate mediante transistor usati come condensatori* Devono essere periodicamente rinfrescate (a causa delle correnti di perdita che tendono a scaricare i condensatori)* Offrono grandi capacità (elevata integrazione) ma sono più lente delle SRAM) SDRAM (Synchronous DRAM)* SDR (Single Data Rate), dati e indirizzi controllati dallo stesso clock (133MHz)* DDR (Double Data Rate): leggono sia nel fronte di salita che in quello di discesa (333/400 MHz)
Gerarchia di Memoria (1/2)+ In generale vogliamo massima capacità e massima velocità al minimo costo, Le memorie a semiconduttore sono molto veloci, poco
capienti e molto costose, Le memorie di massa (dischi, CD, nastri, ...) sono molto capienti, poco veloci e poco costose+ Conviene decidere dove mettere i dati in base al
loro utilizzo, Dati letti/scritti di frequente, in memorie veloci (e poco capienti), Dati letti/scritti di rado, in memorie capienti (e lente)+ Necessità di spostare i dati all’interno di una
Gerarchia di Memoria (2/2)- Registri e cache sono integrati nello stesso chip con la ALU. Velocità massima di accesso da
parte della ALU- La memoria centrale è collegata ad alta velocità con il chip che contiene la ALU. Comunque la ALU lavora sui
registri e sulla cache- Memorie flash e dischi rigidi tendono ormai ad essere sempre più equivalenti in termini di costo e velocità- CD e DVD sono ottimi per la memorizzazione per lunghi periodi di tempo. Memorizzazione ottica Nastri
Dischi Magnetici (1/3)/ Alluminio con rivestimento magnetizzabile/ Tempo di accesso dell’ordine dei millisecondi0 Nanosecondi per i registri/ Sigillati in fabbrica/ Organizzati in cilindri0 Tracce alla stessa
distanza dal centro/ Latenza dovuta alla rotazione
1 Ogni traccia è organizzata in settori2 Preambolo per il posizionamento della testina2 Dati (payload)2 Codice per la rilevazione/correzione di errori 2 Gap tra i settori
Dischi Magnetici (2/3)3 L’evoluzione storica è passata per 4 Dischi rigidi Winchester, anni ’704 Floppy disk, anni ’704 Dischi IDE (Integrated Drive Electronics) negli anni ’80 e EIDE (Extended IDE)4 Dischi SCSI (Small Computer System Interface), 1986, e SCSI-2, 19944 RAID (Redundant Array of Independent Disks)5 Gli stessi dati vengono scritti su vari dischi (in modo
trasparente)5 Consente (in modo trasparente) di rilevare/correggere eventuali errori5 Maggiore affidabilità nella memorizzazione dei dati
Livelli di Sistema (1/3)6 Dal punto di vista dell’utilizzatore (programmatore) vogliamo astrarre dai dettagli fisici del calcolatore7 Offrire all’utilizzatore la stessa macchina però vista a livelli
di astrazione sempre superiori6 Si realizza (al di sopra della macchina reale) una macchina virtuale astratta che abbia le funzionalitàdesiderate e che sia facile da utilizzare 6 L’utente interagisce con la macchina virtuale e ogni comando viene tradotto (interpretato o compilato) nei corrispondenti comandi sulla macchina fisica6 Non vi sono limiti al numero e al tipo di macchine virtuali
Livelli di Sistema (2/3)8 Ogni macchina astratta identifica un livello di sistema8 Ogni livello viene definito con9 Medium, insieme di concetti che il
livello processa9 Componenti, parti atomiche composte per realizzare il sistema9 Regole di composizione che governano come le componenti possono essere assemblate9 Regole di comportamento che individuano: Il comportamento dei singoli
componenti: Il comportamento del sistema in base alla sua organizzazione (architettura) Livello Elettronica Digitale
Livelli di Sistema (3/3); Livello logico< Medium: singoli bit< Componenti: porte logiche elementari< Regole di composizione: come le porte logiche possono essere collegate< Regole di comportamento: tabelle di verità delle porte logiche e comportamento delle strutture composte (e.g., anelli di retroazione nelle reti logiche sequenziali asincrone); Livello elettronica digitale< Medium: segnali elettrici di corrente e tensione< Componenti: transistor, resistenze, ...< Regole di composizione: come i transistor possono essere collegati tra loro e con le resistenze, ...< Regole di comportamento: modelli fisici del comportamento dei transistor e delle strutture composte
Macchina di Von Neumann= Von Neumann collaborò alla realizzazione dell’ENIAC= Inventò un architettura che èancora oggi alla base di quasi tutti i calcolatori= La macchina di Von Neumann èpensata solo per fare calcoli
Livello Linguaggio Macchina (1/3)> Al livello identificato dal linguaggio macchina, il calcolatore è formato da? ALU (Arithmetic Logic Unit)? FPU (Floating Point Unit), non sempre presente? Registri? Memoria centrale? Stack> Le operazioni base sono ? Quelle offerte dalla ALU e dalla FPU@ Che influenzano il contenuto dei registri? Trasferimento di dati tra registri, memoria e stack> È a tutti gli effetti una macchina di Von Neumann
Livello Linguaggio Macchina (3/3)B A livello del linguaggio macchina, di solitoC Lo stack è una porzione della memoria centraleC I bus non vengono controllati esplicitamenteD Copiare il contenuto di R1 in R2 non richiede di controllare il bus in modo esplicitoC I due bus principali sono realizzati mediante diversi busD Il bus verso la memoria è realizzato mediante un bus dati ed un bus indirizziC Lo scambio di dati con i dispositivi di I/O avviene
attraverso la memoria centraleD I dispositivi vengono controllati esplicitamente dal programmatoreD I dispositivi generano segnali che il programmatore vede
Memoria CentraleE Memoria a semiconduttore di tipo RAM che permette di leggere/scrivere dati (di larghezza fissa) in base ad un indirizzoF L’accesso richiede un
tempo indipendente dall’indirizzoE Alcune zone sono riservate
per usi particolariF E.g., buffer di l’I/O, memoria video, ...
Stack (1/3)G Una struttura dati è detta sequenziale se i dati possono solo essereH Aggiunti (per
memorizzarli)H Rimossi (per leggerli)G La cronologia delle modifiche identifica il primoe l’ultimo datoG Due politiche possibiliH Code, politica FIFO (First-
In-First-Out)H Pile (o stack), politica LIFO (Last-In-First-Out)
Stack (2/3)I Le operazioni su uno stack sonoJ Push, aggiungi in testa
alla pilaJ Pop, rimuovi dalla testa della pilaI AttenzioneJ Non è possibile fare pop se la pila è vuotaJ Non è possibile fare push se la pila è piena (pila limitata)
Ciclo Fetch/ExecuteM Viene letta un’istruzione dalla memoria (fetch dell’istruzione)N L’ istruzione è codificata mediante un numero detto codice operativoN L’indirizzo da cui leggere l’istruzione è memorizzato in un registro dedicato detto PC (Program Counter)N L’istruzione viene memorizzata nel registro IR (Instruction Register)M Vengono letti gli eventuali operandi dalla memoriaN Gli operandi vengono memorizzati in registri di uso generale (general purpose register)N È l’istruzione ad indicare quanti operandi servono e in quali registri memorizzarliM Viene eseguita l’istruzione richiestaN Se l’istruzione produce un risultato viene memorizzato in un registroM Se l’istruzione lo prevede, vengono scritti gli eventuali risultati nella
memoriaN È l’istruzione (o i suoi operandi) ad indicare a quale indirizzo scrivere i risultatiM Viene incrementato il PC (adeguatamente) ed il ciclo ricomincia
Calcolatori RISC e CISC (1/3)O Scegliere quante e quali istruzioni fornire al programmatore del linguaggio macchina dipende daP Potenzialità effettive dell’hardwareQ E.g., operazioni implementate nella ALUP Vincoli intrinseci dell’hardwareQ E.g., dimensioni dei registriP Altre decisioni (di progetto) su quanto complesso realizzare
l’hardwareQ Costi, utilizzi previsti del sistema, complessità del progetto, ...O Con il termine ISA (Instruction Set Architecture) si intende l’insieme delle istruzioni del linguaggio macchinaO Tipicamente si usano due linee guida per progettare una ISAP RISC (Riduced Instruction Set Computer)P CISC (Complex Instruction Set Computer)
Calcolatori RISC e CISC (2/3)R Calcolatori RISC (e.g., PowerPC, ...)S Insieme di istruzioni ridotto (pocheistruzioni)S Le poche istruzioni offerte implementanofunzionalità molto sempliciS Le poche istruzioni offerte sono molto velociT L’hardware è ottimizzato per eseguire quelle poche istruzioni
(che sono anche semplici)S A parità di tecnologia, ridurre il numero e la complessitàdelle istruzioni consente di integrare più memoria (registri e cache) nella CPUT Minore necessità di scambiare dati con la memoria centrale
Calcolatori RISC e CISC (3/3)U In ultima analisi, scegliere tra un progetto tipo RISC o CISC dipende da quanto vogliamo realizzare mediante il softwareV 1 istruzione CISC ≈ 5/6 istruzione RISCV 1 istruzione RISC ≈ 10 volte più veloce di 1 istruzione
CISCV Servono compilatori capaci di sfruttare al meglio le caratteristiche delle istruzioni (compilatori con fase di ottimizzazione del codice generato)U Le istruzioni RISC sono pensate perV Poter essere messe in esecuzione velocementeV Sfruttare al meglio la pipeline interna alla CPU
W Ogni istruzione passa attraverso una serie di fasi per essere completataW Ogni fase è implementata da moduli hardware diversiX Possibilità di sfruttare il parallelismo sui vari moduli hardwareX E.g., periodo di clock 2ns (10 ns per istruzione), sfruttando la pipeline si
lavora a 500MIPS (Millions of Instructions Per Second) anziché 100MIPS
Pipeline e Throughput (2/2)Y Due istruzioni A e B possono essere messe in pipeline se B può iniziare prima che termini A(senza causare problemi)Z E.g. (semplificando un po’), mem[0]= R1, mem[1]=R2Y Realizzare una pipeline richiedeZ Istruzioni pensate per essere messe in pipelineZ Struttura hardware aggiuntiva progettata appositamenteY Throughput: numero di istruzioni che iniziano nell’unità di tempoZ A regime, il throughput misura la velocità di una CPUZ La pipeline è pensata per aumentare il throughput
Linguaggio Assembly (1/3)[ Quando si parla di linguaggio assembly si intende un linguaggio costituito da codici mnemonici corrispondenti alle istruzioni del linguaggio macchina[ L’assembly fornisce altre facilitazioni al programmatore\ Etichette simboliche per variabili e indirizzi\ Strumenti per l’allocazione in memoria di costanti\ Preprocessore (macro, inclusione di file, ...)[ Un programma detto assemblatore (assembler) traduce i sorgenti assembly in sequenze di istruzioni in linguaggio macchina\ Di solito, l’assemblatore prevede la presenza di un sistema
operativo\ Il codice generato (linguaggio macchina) è pensato per essere caricato e posto in esecuzione da un sistema operativo
Linguaggio Assembly (2/3)] Un programma (breve)scritto in assembly èsolitamente 2/3 volte più veloce di un equivalente scritto in C] L’ottimizzazione dipiccole porzioni dicodice (tuning) è una tecnica per migliorare le prestazioni dei programmi] L’assembly è spesso^ L’unico linguaggio di programmazione per sistemi
industriali basati su micro-controllori^ Ancora utile in applicazioni real-time
Linguaggio Assembly (3/3)] Rispetto all’uso di un linguaggio ad alto livello, sviluppare un programma in assembly^ Richiede molto più tempo^ È più rischioso dal punto di vista degli errori di codifica
(bug)^ Offre minori possibilità di riuso di codice] In generale, si ritiene che l’uso di un linguaggio ad alto livello mediante un compilatore con una buona fase di ottimizzazione consenta di sfruttare il meglio dei due approcci^ Il GCC (GNU C Compiler) ha varie fasi di ottimizzazione
che generano codice sempre più compatto ed efficiente a scapito del tempo richiesto per la compilazione
Assembly IA-32_ IA-32 è il linguaggio macchina utilizzato dai processori x86-compatibili a 32 bit` Intel 80386, Intel Pentium, AMD Athlon, ..._ Anche se hanno lo stesso linguaggio macchina, le CPU hanno prestazioni diverse` Sono compatibili, non sono equivalenti_ Verrà utilizzato il GAS (GNU Assembler) come assemblatore di riferimento` Sintassi tipica non compatibile con altri assemblatori` Utilizzabile sia con Microsoft Windows (disponibile con
Assemblatore e Linker (1/2)a In generale, l’assemblatore genera codice in linguaggio macchinab Non ancora pronto per essere avviato dal sistema operativoc E.g., non è detto che sia presente un punto d’ingresso (funzione main)b Non completo perché potrebbero mancare dei collegamenti esternia Un file generato dall’assemblatore prende il nome di codice oggetto(della compilazione)a Dato un insieme di codici oggetto, il linker genera un codice eseguibileb Pronto per essere avviato dal sistema operativob Completo di tutti i collegamentic Tranne eventuali collegamenti che vengono risolti dal sistema operativo prima
dell’effettiva attivazione (dal modulo loader del sistema operativo)a I codici oggetto che il loader del sistema operativo collega prendono il nome di shared object (nomenclatura Unix/Linux) o DLL (Dynamic Link Library, nomenclatura Microsoft Windows)
d L’assemblatore GAS viene invocato con il comando as o gcc -Sas -o <object>.o <source>.asmd Il linker GNU viene invocato con il comando ld o (più semplicemente)
Tipicità della Sintassi GASd La sintassi GAS (detta anche AT&T) non è compatibile con la sintassi Microsoft/Intel (usata da MASM, TASM, NASM, ...)d Per le operazioni a due operandi, la sintassi GAS prevede che venga prima indicata la sorgente e poi la destinazionee Nella sintassi Microsoft/Intel è l’oppostod La sintassi GAS prevede che ogni costante non preceduta da $ o %sia un indirizzo di memoriae Gli assemblatori Microsoft/Intel non adottano nessuna convenzioned La sintassi GAS, i nomi dei registri vengono preceduti da %e Non viene richiesto dagli assemblatori con sintassi Microsoft/Inteld La sintassi GAS, le costanti vengono precedute da $e I numeri esadecimali si indicano con il prefisso 0x (come in C)d La dimensione degli operandi nella sintassi GAS viene indicata esplicitamente nel codice operativoe Si usano i suffissi b (8 bit), w (16 bit) e l (32 bit)e Nella sintassi IntelMicrosoft/, i suffissi non sono richiesti
Sorgente Assembly (1/4)f Un file sorgente assembly è un file di testo (ASCII) formato da una lista di statementf Ogni statement ha un formato fisso di 4 campi (tutti opzionali, in ordine fissato)f I 4 campi sono (in ordine)g Campo label, un etichetta che identifica univocamente
l’indirizzo in memoria dello statementg Campo opcode, una stringa (mnemonica) corrispondente al codice operativog Campo operandi, gli operandi dell’istruzioneg Campo commento
Sorgente Assembly (2/4)h Una label è una stringa seguita da ‘:’i La stringa inizia con una letterai La stringa può contenere lettere, cifre e alcuni caratteri speciali (usiamo solo ‘_’)h Gli opcode sono parole chiave che
l’assemblatore riconoscei Istruzioni, che vengono tradotte nelle equivalenti del linguaggio macchinai Direttive, che guidano l’assemblatore nella generazione del codice oggettoj Il GAS prevede che le direttive inizino con il simbolo ‘.’
Sorgente Assembly (3/4)k Gli operandi possono essere di vario tipol Costanti (operandi immediati), registri, indirizzi di memorial Se sono presenti due operandi, il primo è detto sorgente e il secondo destinazionek I commenti sono fondamentali nella
programmazione assemblyl Ritenuti più importanti rispetto alla pratica di programmazione in linguaggi di alto livellol Iniziano con un ‘#’l Tutti gli statement andrebbero commentati
Modello della Memoria IA-32 (1/3)o IA-32 ha due tipi di modello di memoria segmented e flatp Segmented, la memoria è divisa in 16k segmenti
di 4 Gbyte l’unop Flat, la memoria è un unico segmento di 4 Gbyteo Tipicamente, i sistemi operativi più comuni (Microsoft Windows e Linux) utilizzano solo il modello flat (indirizzi a 32 bit)p Offre il vantaggio che un indirizzo può essere
memorizzato completamente in un registrop Il GAS si riferisce implicitamente al modello flat
Modello della Memoria IA-32 (2/3)q I tipi dato di riferimento di IA-32 sono byte (8 bit), word (16 bit) e double word (32 bit)q Byter 8 bit che iniziano a qualsiasi indirizzor Numerati da 0 a 7, il bit meno significativo è il bit 0q Wordr 2 byte che iniziano a qualsiasi indirizzor Numerati da 0 a 15, il bit meno significativo è il bit 0r L’indirizzo del byte meno significativo coincide con l’indirizzo della word q Double wordr 4 byte che iniziano a qualsiasi indirizzor Numerati da 0 a 31, il bit meno significativo è il bit 0r L’indirizzo del byte meno significativo coincide con l’indirizzo della double wordq IA-32 è un’architettura little endian, i byte meno significativi sono ad un indirizzo inferiore di quelli più significativir Altre CPU (e.g., PowerPC) sono big endianq IA-32 è ottimizzato per word allineate ad indirizzi pari e per double word allineate ad indirizzi divisibili per 4r Anche se non viene richiesto che l’allineamento sia rispettato
Tipi Dato IA-32s Varie operazioni di IA-32 lavorano su tipi dato diversit Interi: byte, word o double word con segno. Rappresentati in complemento a 2. Il bit di segno è il più significativo (0 positivo, 1 negativo)t Ordinali (naturali): interi senza segnot Indirizzi vicini: indirizzo logico di 32 bit contenente un offset all’interno di un segmento. È il tipo di indirizzo usato nel modello di memoria flatt Indirizzi lontani: indirizzo logico di 48 bit contenente 16 bit per individuare un segmento e 32 bit per individuare un offset all’interno di un segmento. Viene utilizzato nel modello di memoria segmentedt Stringhe (di byte): sequenza continua di byte (da 0 a 4 Gbyte)t Altri che non consideriamo (BCD, ...)
Registri IA-32 (2/2)u IA-32 contiene 8 registri a 32 bitv EAX, EBX, ECX, EDX, EBP, ESP, ESI e EDIv Per compatibilità con le architetture Intel a 8/16 bit, la parola bassa di ogni registro può essere indirizzata in modo esplicitow AX, BX, CX, DX, BP, SP, SI e DIv I singoli byte dei registri a 16 bit AX, BX, CX e DX possono essere indirizzati esplicitamentew Byte alti: AH, BH, CH e DHw Byte bassi: AL, BL, CL e DLu Alcune istruzioni prevedono che gli operandi siano in
particolari registriv Ottimizza il numero e l’espressività dei codici operativiv Supporta la retro-compatibilità con le architetture Intel a 8/16 bit
Registri IA-32 Dedicatix EIP (Instruction pointer) contiene l’indirizzo della prossima istruzione da eseguirey Viene incrementato automaticamente durante il fetch delle istruzioniy Modificato dalle istruzioni di saltoy I programmi non lo modificano esplicitamentex EFLAGS (Extended Flags) contiene i bit di stato della CPUy I bit principali sono i cosiddetti condition codey Questi bit vengono scritti ad ogni ciclo dalla ALU e riflettono il risultato
dell’operazione più recentey I condition code (flag) più comuni sonoz CF (bit 0): 1 quando il risultato ha determinato riporto (carry)z PF (bit 2): 1 quando il risultato ha un numero pari di 1z AF (bit 4): 1 quando il risultato ha determinato riporto intermedio sul bit 3 (utile in codifica BCD, Binary Coded Decimal)z ZF (bit 6): 1 quando il risultato è zeroz SF (bit 7): bit segno, 1 quando il risultato è negativoz OF (bit 11): 1 quando il risultato ha causato overflow con operazioni in aritmetica intera con segno (complemento a 2)
Registri di Segmento IA-32{ IA-32 prevede 6 registri di segmento usati per identificare i 6 segmenti di memoria in uso da un programma| CS, DS, SS, ES, FS e GS{ In particolare| CS contiene l’indirizzo del segmento di codice (di testo)
attuale| DS contiene l’indirizzo del segmento dati attuale| SS contiene l’indirizzo del segmento usato per lo stack | ES, FS e GS contengono indirizzi di segmento usati dal programma per propri scopi{ In modalità di indirizzamento flat, il programmatore
Modalità di Indirizzamento IA-32} Gran parte delle istruzioni assembly consentono di copiare dati nei registri e nella memoria} Le modalità di reperimento dei dati da copiare sono dette modalità di indirizzamento~ Le varie modalità di indirizzamento indicano i modi in cui la CPU può
reperire gli operandi delle istruzioni~ Un operando può specificare cose diverse� Un registro, una costante, un indirizzo di memoria, un indirizzo di memoria al quale sommare (implicitamente) un offset, ...} Consideriamo l’istruzione movl SRC,DST che viene utilizzata per
copiare una double word da SRCa DSTmovl $0x10,%eax # immediato (eax=0x10)movl 0x100,%eax # diretto o assoluto (eax=mem[0x100] )movl %ebx,%eax # di un registro (eax=ebx)movl (%ebx),%eax # indiretto (eax=mem[ebx])movl -2(%ecx),%eax # indiretto con indice (eax=mem[e cx-2])
Indirizzamento Immediato� L’operando è un valore costante� La lunghezza del valore costante (1, 2, o 4 byte) dipende dal tipo di operazione e dai registri coinvoltimovb $10,%al # bytemovb $0xFF,%ah # byte
movw $1000,%ax # word
movl $0x10FFEEEE,%eax # double word� Per caricare la costante 0 in un registro è preferibile usare xorl %eax,%eax� Questa operazione non richiede il caricamento di nessun
Indirizzamento Diretto (o Assoluto)� L’operando specifica un indirizzo di memoriamovl 0x100,%eax # double word movw 0x100,%ax # wordmovb 0x100,%al # bytemovl %eax,0x100 # double word movw %ax,0x100 # wordmovb %al,0x100 # byte� Attenzione: IA-32 è little endian e quindi il byte basso è il primo memorizzato a partire dall’indirizzo indicato
Indirizzamento Mediante Registri� Indirizzamento di un registroUn registro può essere usato per contenere un dato da scrivere o per ricevere un dato in scritturamovb %al,%ah� Indirizzamento indirettoL’operando che è letto o scritto in memoria all’indirizzo specificato dal contenuto di un altro registromovl %eax,(%ecx)movl (0x100),%eax� Indirizzamento indiretto con indiceL’indirizzo di memoria è determinato a partire da un valore costante a cui viene sommato il contenuto di un registro (usato come indice)movl %eax,vettore(%ecx)movl %eax,vettore(%ebx,%ecx,4)
Istruzioni Assembly IA-32� IA-32 è un’architettura CISC ed è dotata di molte istruzioni� Copia e spostamento di valori da/verso la memoria ed i registri� Aritmetica intera� Operazioni logiche e di spostamento di bit� Istruzioni di salto in-/condizionato� Manipolazione di stringhe� Aritmetica in virgola mobile� MMX (Multi-Media eXtension)� Supporto al sistema operativo� Controllo dell’I/O� ...� Ogni istruzione, può essere utilizzata in modo diverso a secondadelle modalità d’indirizzamento� Esistono però delle limitazioni che impediscono l’utilizzo di certi registri
Salti In-/Condizionati� Le istruzioni di test e salto vengono utilizzate per realizzare un salto ad un’etichetta specificata� Incondizionato, il salto avviene sempre� Condizionato, il salto avviene solo in certe
condizioni� Le condizioni sono verificate sulla base dei flag di stato della CPU (flag SF, ZF, ...)� I salti condizionati sono utilizzati per
implementare i costrutti while e for dei linguaggi ad alto livello
testX e cmpX� testX X,YEsegue l’AND di X ed Y. Il risultato non viene memorizzato ma viene utilizzato per impostare i flag SF, ZF e PF� SF viene impostato al valore del bit più significativo del risultato� ZF viene impostato a 1 se il risultato è 0� PF viene impostato a 1 se il risultato ha un numero pari di 1� cmpX X,YEsegue Y-X . Il risultato non viene memorizzato ma viene utilizzato per impostare i flag CF, SF, ZF, PF, OF e AF� CF viene impostato a 1 se il risultato ha determinato un riporto� AF viene impostato a 1 se il risultato ha determinato riporto
intermedio sul bit 3 � OF viene impostato a 1 se il risultato ha causato overflow con operazioni in aritmetica intera con segno (complemento a 2)
jmp e jCC (1/2)� jmp ADDREsegue un salto incondizionato all’indirizzo ADDR. Il salto viene eseguito caricando in EIP il valore ADDR (relativo o assoluto)jmp fine # indirizzo relativojmp *(%edx) # indirizzo assoluto� jCC ADDRSalta all’indirizzo ADDRse la condizione espressa dal condition code CCè veracmpl %eax,%ecxje addr # salta se %eax = %ecxcmpl %eax,%ecxjl addr # salta se %ecx < %eax (unsigned)cmpl %eax,%ecxjle addr # salta se %ecx <= %eax (unsigned)
cmovCC, jcxz e jecxz� cmovCCX SRC,DSTCome movXma la copia viene eseguita solo se il condition code CCè vera cmpw %ax,%bxcmovzw %cx,%dx # se ZF=1 (%ax=%bx) %cx=%dx� jcxz e jecxz usano i registri %cx ed %ecx come condizione per i saltijcxz ADDR # salta ad ADDR se %cx=0jecxz ADDR # salta ad ADDR se %ecx=0ADDRè un indirizzo relativo ad 8 bit (se l’indirizzo si trova distante dal punto di salto l’assemblatore segnala un errore)
loop e loopCC� loop ADDRUn’istruzione compatta e ottimizzata per l’esecuzione di cicli che utilizza %ecx come contatore%ecx viene decrementato di un’unità e viene confrontato con 0; se diverso salta ad ADDRADDRpuò essere solo un indirizzo relativo a 8 bit� loopCC ADDRContinua a saltare ad ADDRmentre %ecx è diverso da 0 e la condizione CCè veraDue condizioni posso causare l’uscita dal ciclo (è sufficiente che se ne verifichi una)� %ecx vale 0� CCfalsa (CCpuò essere E, Z, NE, NZsul flag ZF)
addX e subX� addX SRC,DSTEsegue la somma di DSTe SRC; il risultato è posto in DSTIn base al risultato sono impostati i flag: OF, SF, ZF, AF, CF e PF� subX SRC,DSTEsegue la sottrazione DST-SRCe memorizza il risultato in DSTIn base al risultato sono impostati i flag: OF, SF, ZF, AF, CF e PF
� mulX SRCEsegue una moltiplicazione senza segnoSi comporta in modo diverso a seconda della dimensione dell’operando SRC� Se l’operando è a 8 bit, la moltiplicazione è eseguita tra %al e SRCe il risultato
copiato in %ax� Se l’operando è a 16 bit, %axviene moltiplicato per SRCe il risultato è memorizzato in %dx:%ax (in %dxsono contenuti i 16 bit più significativi e in %ax i 16 bit meno significativi)� Se l’operando è a 32 bit %eax viene moltiplicato per SRCe si fa uso di %edx per memorizzare il bit più significativi del risultato (che è a 64 bit)� Attenzione: non è possibile usare un operando immediato per SRC
� divX SRCEsegue una divisione senza segnoSi comporta in modo diverso a seconda della dimensione dell’operando SRC� Se l’operando è a 8 bit, la divisione è eseguita tra %axe SRCe il quoziente è in %al
e il resto in %ah� Se l’operando è a 16 bit, %dx:%ax viene diviso per SRCe il quoziente è in %ax, mentre il resto è in %dx� Se l’operando è a 32 bit %edx:eax viene diviso per SRCe si fa uso di %eax per il quoziente e di %edx per il resto� Attenzione: SRC viene generato un errore (eccezione run-time)
imulX e idivX� imulX esegue una moltiplicazione intera con segno (gli operandi sono in complemento a 2)� imulX prevede due formati principaliimulX SRCimulX SRC,DST # DST=DST*SRCNel primo caso il funzionamento è analogo a mulX(per quanto riguarda i registri utilizzati)Nel secondo caso SRCpuò essere anche un valore immediato� idivX esegue una divisione intera con segno in modo analogo a divX
incX e decX� incX DSTIncrementa di 1 il valore specificato da DST(senza alterare il flag CF)Attenzione: se DSTha raggiunto il valore massimo l’istruzione di incremento causa overflow senza che CF o OF vengano impostatiL’unico flag utilizzabile per verificare l’overflow è ZF� decX DSTDecrementa di 1 il valore specificato da DST (senza alterare il flag CF)Attenzione: per verificare undeflow (traboccamento sotto lo zero) può essere utilizzato il flag di segno SF
Istruzioni Logiche� notX DSTComplementa il valore di DSTe lo scrive in DST� andX/orX/xorX SRC,DSTAND/OR/XOR tra SRCe DSTe il risultato viene sovrascritto in DST� salX/sarX N,DSTShift aritmetico a sinistra/destra in DSTdi un numero di bit specificato da N (compreso tra 0 e 31)N può essere un valore immediato a 8 bit oppure il registro %clNel caso di salX , per ogni shift di 1 posizione il bit meno significativo assume valore 0, mentre il bit più significativo finisce in CFNel caso di sarX , per ogni shift di 1 posizione, il bit meno significativo fuorisce e finisce in CF, mentre il bit più significativo MSB estende il segno (stesso valore del precedente MSB)� shlX/shrX N,DSTShift logico a sinistra/destra in DSTdi un numero di bit specificato da N (compreso tra 0 e 31)N può essere un valore immediato a 8 bit oppure il registro %clshlX opera in modo identico a salXshrX a differenza di sarX non estende il bit di segno ma pone a 0 l’MSB entrante
Stack in IA-32� IA-32 prevede stack multipli, ognuno in un segmento separato di memoria� Il registro ESP (Extended Stack Pointer) individua la cima dello stack� Lo stack è push-down ed è manipolato da� Istruzioni di push e di pop� Chiamate a procedura (e relativo ritorno)� Interrupt� EBP (Extended Base Pointer) è un registro chiamato frame base pointer ed è il più utile per manipolare direttamente lo stack� Contiene l’indirizzo base dello stack della procedura corrente� Viene modificato solo all’ingresso ed all’uscita da una procedura� L’accesso in lettura (con offset costante) è ottimizzato
pushX e popX� La gestione dello stack in IA-32 prevede solo dati a 32 bit o 16 bit� È sempre preferibile tenere lo stack allineato a 32 bit� pushX SRCPone il valore SRCsulla cima dello stackpushl %eax� popX DSTRimuove il valore alla cima dello stack e lo salva in DSTpopl %eax
call e ret (2/2)� call ADDRProsegue l’esecuzione dall’indirizzo ADDRPrima di eseguire il salto memorizza il valore di %eip (che punta all’istruzione successiva a call ) in cima allo stack (il valore di %esp cambia a seguito di call e sulla cima dello stack viene caricata una double word equivalente a %eip)� retQuando una procedura termina (con ret ), un’istruzione tipo popl %eip causa il ritorno all’istruzione successiva al punto in cui è stata chiamata la procedura� Attenzione: non è mai possibile manipolare %eip direttamente� Usando call e ret è possibile realizzare delle procedure utilizzando i registri (o lo stack) per passare parametri ed i valori di ritorno� In assembly, non ci sono differenze tra procedure e funzioni
Procedure e Funzioni� call e ret da soli non bastano nei casi reali� Servono delle convenzioni sul passaggio dei parametri e sui valori di ritorno� È importante essere inter-operabili con procedure
scritte con linguaggi di alto livello� Poter chiamare/poter essere chiamati� Ogni compilatore può decidere di adottare specifiche convenzioni (spesso i compilatori Pascal e C adottano convenzioni diverse)� Di solito (ma praticamente sempre in ambiente Linux o Microsoft Windows) si adottano le convenzioni del C
Stack Frame (1/2) Area di stack (anche detta record di attivazione) che viene creata al momento della chiamata ad una procedura e contiene¡ Indirizzo di ritorno¡ Parametri attuali passati alla procedura¡ Registri salvati con lo scopo di ripristinarli all’uscita della procedura¡ Variabili locali alla procedura Viene creato come segue¡ Il chiamante mette i parametri attuali in cima allo stack e chiama la
procedura (con call )¡ L’uso di call mette in cima allo stack l’indirizzo di ritorno¡ La procedura chiamata salva %ebp nello stack e imposta %ebp e %esp¡ Se servono variabili locali, viene sottratto ad %esp lo spazio necessario Viene distrutto all’uscita dalla procedura¡ La procedura chiamata ripristina %esp (con %ebp), quindi ripristina %ebp e ritorna (con ret )¡ Il chiamante trova il risultato della procedura (funzione) in %eax e toglie i parametri dallo stack (sommando una costante ad %esp)
Variabili Locali¢ Le variabili locali ad una procedura sono create nello stack frame appena sotto %ebp¢ Si riserva lo spazio sottraendo la loro dimensione complessiva (in byte) a %espprocedura:
Manipolazione di Stringhe£ Le stringhe sono vettori di byte e IA-32 mette a disposizione una serie di istruzioni ottimizzate per la loro manipolazione ¤ Indipendentemente dalla codifica ASCII, trattano gli
elementi come byte¤ Utilizzano due registri dedicati ESI (Extended Source Index) e EDI (Extended Destination Index) utilizzati come indirizzo dell’elemento corrente nella stringa sorgente o destinazione£ Non vengono comunemente usate dai compilatori
Istruzioni Floating-Point¥ IA-32 introduce registri aggiuntivi dedicati all’unità floating-point¦ Anche se accessibili singolarmente, vengono trattati come uno stack¥ In base alle loro funzionalità, le operazioni floating-point possono essere raggruppate in¦ Trasferimento dati: carica (FLD), salva (FST), ...¦ Operazioni: somma (FADD), sottrazione (FSUB), moltiplicazione (FMUL), divisione
(FDIV), radice quadrata (FSQRT), ...¦ Confronto: non è possibile confrontare con cmpX valori floating point, sono quindi necessarie operazioni di confronto dedicate (FCOM, ...)¦ Funzioni transcendenti: seno (FSIN), coseno (FCOS), logaritmo (FYL2X), esponenziale (F2XM1), ...¦ Caricamento di costanti note: quali 0, 1, § , e, ... nei registri senza dover caricarne il valore dalla memoria¦ Controllo dell’FPU: inizializzazione (FINIT), sincronizzazione, ...¥ Tutte le operazioni aritmetiche floating point sono eseguite in formato doppia
precisione estesa IEEE 754 (80 bit)¦ Se i risultati devono essere scritti in variabili o in memoria in formato più corto viene eseguita una conversione
SSEª A partire dal Pentium III è stato introdotto SSE (Streaming SIMD Extensions) « Aggiunge 8 nuovi registri a 128 bit« Sui nuovi registri è possibile eseguire operazioni SIMD su floating point
in singola precisione« Estende anche le funzionalità MMX« ..ª A partire dal Pentium 4 (nel 2001) è stato introdotto SSE2« Consente di eseguire operazioni SIMD su floating point in doppiaprecisione« Estende ulteriormente MMX« ...ª Le istruzioni SSE3 sono state introdotte agli inizi del 2004 con il
Pentium 4« SSE3 aggiunge 13 nuove istruzioni rispetto a SSE2« ...
