Macchine Astratte Corso: Architettura degli Elaboratori Docente: Franco Barbanera Lucidi by G.Bella...

Macchine Astratte

Corso: Architettura degli Elaboratori

Docente: Franco Barbanera

Lucidi by G.Bella (modificati by F.Barbanera)

UNIVERSITA’ DI CATANIADip. di Matematica e Informatica

(anche dette Macchine Virtuali)

F. Barbanera, G. Bella 2 Macchine Astratte v.2.2

Cosa significa “computare”?

computazione3+5 8


Genericamente:

input output

procedimento effettivo

Computazione e’ una trasformazione di informazione da una forma implicita ad una esplicita,mediante una sequenza di passi computazionali unitari.

Buono, ma troppo generico


Modello Computazionale

• informazione• passo computazionale unitario

Un modello computazionale fornisce una formalizzazione delle nozioni di

Un modello computazionale e’ quindi unadefinizione piu’ concreta di computazione.


Alcuni modelli computazionali

Gödel, basato sulla logicaChurch, basato sul calcolo di funzioniPost, basato sulla manipolazione di stringhe di caratteriTuring, basato su una macchina con un nastro e una testina…

nome dell’inventore


un nastro infinito, suddiviso in celle, ciascuna capace di contenere un qualunque simbolo di un alfabeto

una testina movibile, capace di leggere e/o scrivere un simbolo in una cella

un controllo finito, che memorizza lo stato corrente

un insieme di quintuple

Una quintupla (istruzione) descrive cosa deve scrivere la testina e dove spostarsi (dx o sx) quando la testina legge un certo simbolo e si è in un certo stato corrente .

composta da

Il modello computazionaledi Alan Turing (1936):

La Macchina di Turing (TM)


Modello Computazionale di Turing

•informazione rappresentata da una lista di simboli (contenuti nel nastro)

•passo unitario di computazione come “esecuzione” di una quintupla.


TM alla base della programmazione imperativa

locazione –

assegnamento –

memoria –

stato –

iterazione –

La Macchina di Turing introduce gli elementi essenzialidella moderna programmazione imperativa:


Church: Il Lambda-calcolo

Il lambda calcolo è un altro modello computazionale, basato sui concetti di

- Variabile (in senso matematico)- Applicazione - Astrazione funzionale- Ricorsione E’ alla base della Programmazione Funzionale (Lisp, Haskell,

ML)


Verso una definizione di macchina basata sui concetti introdotti dalle TM, ma non eccessivamente essenziale.


Macchina Astratta (Imperativa)

memoriaoperazioni primitiveoperazioni e strutture dati per gestire il trasferimento dati, ossia leggere gli operandi e memorizzare i risultati delle istruzionioperazioni e strutture dati per gestire il controllo di sequenza, ossia l’ordine di esecuzione delle operazioni del programmainterprete per l’esecuzione del programma

E’ un insieme di algoritmi e strutture dati in grado di memorizzare ed eseguire programmi.


OsservazioniPrecisa corrispondenza fra macchine astratte (imperative) e linguaggi di programmazione (imperativi). IMPORTANTE!!!

Modelli computazionali diversi conducono a nozioni diverse di macchine astratte

La maggioranza delle architetture concrete sono realizzazioni di macchine astratte imperative (per ragioni tecnologiche)


Struttura di una Macchina Astratta


Architettura di Van Neumann

E’ la struttura delle realizzazioni fisiche di Macchine astratte imperative

La CPU (Central Processing Unit) interpreta il Programmae legge i Dati dalla RAM (Random Access Memory).


L’ Interprete

E’ preposto all’esecuzione dei programmi

Coordina il funzionamento delle altre componenti, allo scopo di eseguire un ciclo FETCH/EXECUTE continuamente fino all’esecuzione dell’istruzione primitiva HALT


L’algoritmoInterprete

operazioni primitive

mediante operazioni e strutture dati per gestire il trasferimento dati

mediante operazioni e strutture dati per gestire il controllo di sequenza

si acquisisce

dalla memoria


Esempio di Macchina Astratta

- macchina tradizionale -

memoria: vettore indicizzato di stringhe binarie

operazioni primitive: aritmetico-logiche su stringhe di bit

trasferimento dati: modalita’ per indirizzare la memoria

controllo di sequenza: registro contatore istruzioni (PC) ecc.


Esempi di macchine astratte

lavatricecalcolatriceJVM (Java Virtual Machine)ristorante…


Esempio di Macchina Astratta

- ristorante -memoria: taccuini dei camerieri (input), dispensa (dati), tavole imbandite (output)

operazioni primitive: varie capacita’ culinarie dell’insieme dei cuochi

trasferimento dati: regole per trasferimento ingredienti dalla dispensa ai cuochi

controllo di sequenza: ordine di arrivo delle ordinazioni ai cuochi, ordine di utilizzo degli ingredienti di una ricetta

interprete: camerieri


E l’ Input/Output ?

Fra le componenti di una Macchina Astratta, non abbiamoincluso le strutture dati e gli algoritmi per la gestione dell’ Input/Output.

Difficilmente esse possono essere generalizzate,ma volendo, si potrebbe.


Il Linguaggio Macchina

LM, il linguaggio macchina di M, e’ il linguaggio in cui si esprimono tutti i programmi eseguibili da MLMEST, il linguaggio macchina esteso di M, e’ un linguaggio di stringhe di caratteri direttamente traducibili in LM

Si consideri una Macchina Astratta M

Esempio: un programma in LM e’ una sequenza di vari livelli di tensione per i bit di una memoria fisica; l’equivalente in LMEST e’ un insieme di stringhe di 0 e di 1.


Il Linguaggio MacchinaLM e’ il linguaggio in cui i programmi eseguibili da M vengono rappresentati internamente

LMEST e’ il linguaggio in cui i programmi eseguibili da M vengono rappresentati esternamente

Il medesimo oggetto programma astratto puo’essere rappresentato in ambedue i linguaggi.Quindi non faremo differenza fra i due linguaggi.

Il LOADER carica un programma in LMEST, lo tra-duce in LM e lo carica nella memoria della macchina.


Un binomio inscindibileData una macchina astratta, resta definito il linguaggio di programmazione che e’ il suo linguaggio macchina

Dato un linguaggio di programmazione, resta definita la macchina astratta che lo abbia come suolinguaggio macchina

Macchinaastratta MMacchinaastratta M

LinguaggioLM

LinguaggioLM

spaghetti, insalata, …spaghetti, insalata, …

cuococuoco lavabiancherialavabiancheria

delicato, colori,forte…

delicato, colori,forte…


Complessita’In virtu’ del binomio visto, si puo’ affermare chela complessita’ di una macchina dipende dalla complessita’ del suo linguaggio, e viceversa.Esempio 1. Si supponga che LM preveda il tipo astratto LISTA.Allora, M deve contenere operazioni elementari per realizzare Head, Tail, Length, …ed algoritmi per l’allocazione dinamica della memoria per le liste.

Esempio 2. Si pensi a un moderno HLL (high-level

language)


L’hardware: la realizzazione fisica di una MA

Oggi, e’ tecnicamente possibile realizzare una macchina astratta associata ad un linguaggio di alto livello.

Due degli inconvenienti derivanti sarebbero:- costi della realizzazione- scarsa flessibilita’ della macchina ottenuta

Quindi, in pratica, solo macchine astratte piuttosto semplici vengono realizzate in hardware.


Alternative?In generale, come implementare una Macchina Astratta M ?

Esistono 3 realizzazioni:

• hardware : realizzare M fisicamente

• interpretativa : emulare M mediante una macchina gia’ realizzata

• compilativa : tradurre il linguaggio di M in quello di una macchina gia’ realizzata

gia’

tratta

to


Realizzazione Interpretativa

Sia M la Macchina Astratta da realizzare.Sia M’ una MA gia’ realizzata.(M’ e’ detta macchina ospite)

Si realizzano tutti gli algoritmi e le strutture dati che definiscono le componenti di M mediante programmi e strutture dati di LM’.Se questi ultimi sono memorizzati in una memoria ad alta velocita’, di sola lettura, sullo stesso chip contenente le altre componenti di M’, si parla di interpretazione via firmware.


Realizzazione CompilativaCome nel caso precedente, sia M la Macchina Astratta da realizzare, e sia M’ la macchina ospite.Si traduce l’intero programma scritto in LM in un programma funzionalmente equivalente scritto in LM’.

Tale traduzione e’ eseguita dal compilatore.

Le componenti di M in realta’ non vengono realizzate, ma l’utente ugualmente godra’ delle funzionalita’ di M.


Nasce un problema…

C’e’ una differenza di potenza espressiva fra le due macchine (tra i due linguaggi).

Come calcolare 3+5mentre si dispone di una macchina fisica che puo’ solo incrementare un numero binario?

In generale, la differenza di potenza espressiva fra la Macchina Astratta da realizzare e la macchina ospite esistente, e’ detta semantic gap.


Efficienza della realizzazione

Con l’interpretazione, l’interprete di M e’ realizzato da un programma in LM’, eseguito dall’interprete di M’Con la compilazione, il programma in LM’ potrebbe avere dimensioni enormi, e quindi essere lento; il compilatore stesso e’ molto complicato se LM ed LM’ sono molto diversi

Spesso il semantic gap e’ cosi’ ampio che sia l’interpretazione che la compilazione potrebbero risultare inefficienti (M sarebbe lenta).

Pertanto, si e’ pensato a delle macchine intermedie…


Singola macchinaintermedia

programma in LM

programma in LM

MM

programma in LMi

programma in LMi

MiMi

programma in LM’

programma in LM’

M’M’

macchina che vogliamo realizz

are

macchina interm

edia

macchina gia’ realizz

ata

compilazione

interpretazione

Mi va progettata in modo da massimizzare• compattezza del codice in LMi prodotto• velocita d’interpretazione di Mi su M’


Esperienze praticheMi e’ tipicamente solo un’estensione di M’ poiche’ ne usa il medesimo interprete, potenziato con un insieme di routine dedicate dette run-time system

Java si basa sullo schema appena visto: Mi e’ la JVM (Java Virtual Machine); LMi e’ detto Bytecode; il run-time system e’ detto Java RunTime Environment

Tutte le combinazioni compilazione/interpretazione sono possibili!!!

La singola macchina viene generalizzata a piu’ macchine intermedie all’uopo di maggior flessibilita’ del sistema


Una gerarchia di macchine

computer

reale

per esempio,un HLL


OsservazioneAlcune componenti di una macchina possono essere identiche ad altrettante della macchina ospite.

Esempio. Si immagini di poter utilizzare in C alcune routine per l’aritmetica binaria.

Esempio schematico. Ciascun linguaggio ha componenti precipue (interpretate o compilate nei livelli inferiori) ed altre ereditate immutate.


Tipica gerarchia di macchine in un moderno calcolatore

Il passaggi

o a ciascun

livello intermedi

o colma una parte

del semantic

gap.


Livello 0 – logica digitaleComponenti fondamentali sono le porte logiche (GATES ).

Le porte logiche sono dispositivi analogici, ma fanno da tramite verso quelli binari (e quindi digitali)perche’ realizzano funzionalita’ (Not, And, Or, …) formalizzabili mediante una teoria binaria detta Algebra di Boole.

Combinando variamente le porte logiche, si otterranno i registri, le memorie, le ALU.


Livello 1 - microprogrammazioneComponenti fondamentali sono registri e circuiti digitali che realizzano varie funzionalita’ aritmetico-logiche.

Troviamo anche il datapath, le memorie, l’IFU (Instruction-Fetch Unit).

Nasce il concetto di flusso di informazione poiche’ sequenze di bit viaggiano da una componente all’altra della Macchina Astratta di questo livello, venendo eventualmente elaborate.


Livello 2 – istruzioni macchinaLivello cui ci si riferisce quando si parla di linguaggio macchina.

Istruzioni tipiche sono: ADD, MOVE, SUB, etc…

Tale livello e’ direttamente implementato in hardware nel caso delle architetture RISC, mentre e’ realizzato mediante interpretazione firmware nelle architetture CISC.


Livello 3 – sistema operativo

• FILE e FILE SYSTEM – la prima organizzazione strutturata e gerarchica delle informazioni

• MEMORIA VIRTUALE – la macchina offre un’enorme quantita’ di memoria in piu’ rispetto a quella fisica

• PROCESSI e MULTITASKING – piu’ pezzi di programma in esecuzione indipendente e pseudo-parallela

Esso non copre del tutto il livello sottostante. Molte istruzioni del 2 sono disponibili insieme a nuove, piu’ evolute funzionalita’:

programmare fino a questo

livello e’ per sistemisti


Livello 4 – assemblyE’ il primo a presentare alcune caratteristiche elementari di un linguaggio di programmazione (etichette, variabili globali, procedure,…)

E’ realizzato mediante compilazione. Il compilatore si chiama assembler.

L’assembler e’ tipicamente scritto in istruzioni macchina (di livello 2).


Livello 5 – HLLI moderni linguaggi di programmazione si posizionano a questo livello.

Esistono varianti sia interpretative che compilate di certe macchine di questo livello.(Ad esempio, quella il cui linguaggio e’ il BASIC)Osservazione 1. La JVM si sta consolidando fra i livelli 4 e 5.

Osservazione 2. I livelli descritti sono solo una possibile strutturazione gerarchica di un sistema.


Al di sotto della logica digitalePossiamo individuare almeno 2 livelli:• livello -1 – elettronica circuitale; si

combinano i dispositivi di base (transistor, diodi, etc…) per ottenere le porte logiche

• livello -2 – fisica dello stato solido; si sfrutta la struttura fisica dei solidi e le proprieta’ dei semiconduttori per realizzare dispositivi di base Servono da tramite fra i fenomeni fisici e le

tecniche per l’automazione del calcolo. Immaginare delle Macchine Astratte a tali livelli sarebbe pura speculazione.


Programmazionee livelli di astrazioneUn programma scritto in un HLL aggiunge un livello alla gerarchia.

Esso estende la Macchina Astratta associata all’HLL con nuove strutture dati e nuove operazioni.

Quindi, la potenza di un HLL si puo’ misurare coi meccanismi di astrazione che esso offre.

Nessun linguaggio al momento estende il controllo di sequenza, del trasferimento dei dati, o la gestione della memoria.


ATTENZIONE!!!

In un sistema di calcolo non c’e’ limite ai livelli di MA presenti. Non tutti i sistemi di calcolo hanno il livello microprogrammato (CISC con, RISC senza)

Macchine Astratte Corso: Architettura degli Elaboratori Docente: Franco Barbanera Lucidi by G.Bella...

Documents

Transcript of Macchine Astratte Corso: Architettura degli Elaboratori Docente: Franco Barbanera Lucidi by G.Bella...