INTRODUZIONE
8
programma non alteri alcuna relazione di Input/Output originaria. Questa
trasformazione è affidata ad uno strumento software, il compilatore parallelizzante,
che, sulla scorta della analisi del programma in ingresso, rispettivamente l’Analisi del
Flusso e l’Analisi di Dipendenza Dati, fornisce informazioni utili per l’individuazione
di quali segmenti di programma sono eseguibili in parallelo (parallelismo implicito).
In altre parole per l’annotazione del parallelismo ci si affida al compilatore, che
procederà a scoprire i vincoli strutturali, le dipendenze, presenti in un programma che
impediscono l’esecuzione in parallelo, ed a classificare questi vincoli ed infine, nei
casi in cui è possibile, trasformare il programma (restructuring transformations), così
che essi siamo rimossi.
Ai fini del corretto utilizzo di questi strumenti è previsto un meccanismo di
interazione con l’utente (user friendly tool), tutt’oggi i più moderni sistemi di
compilazione (Parafrase2 [Gir90], SUIF [Hall96], Polaris [Blume96]) sono dotati di
un vasto insieme di comandi ed opzioni (command line flags) e di sistemi per la
visualizzazione grafica e manipolazione della rappresentazione intermedia [CFG99].
In particolare nel caso di sistemi di compilazione sorgente-sorgente, dove l’output
prodotto consiste in una versione parallela del codice in cui il parallelismo è annotato
in un formato che può essere riletto dallo stesso compilatore, l’utente è invogliato alla
costruzione di un processo ciclico di compilazione, dove ad ogni passo, la
parallelizzazione del programma è ulteriormente raffinata, attraverso la combinazione
di conoscenze aggiuntive sulla struttura del programma, fornite dell’utente, e di
tecniche di compilazione.
I compilatori parallelizzanti sono utilizzati prevalentemente per la parallelizzazione di
programmi sequenziali complessi, generalmente con un numero elevato di righe di
codice, in quanto la loro riscrittura mediante l’ausilio di linguaggi di programmazione
con costrutti paralleli sarebbe molto difficoltosa. Tuttavia la ristrutturazione
automatica di programmi sequenziali non fornisce garanzie di miglioramento delle
prestazioni; la qualità del codice ristrutturato può dipendere sia dalla struttura del
programma da implementare sia dalla architettura della macchina su cui il programma
INTRODUZIONE
9
parallelo dovrà operare. Ciò è dovuto al fatto che pur individuando opportunità di
parallelismo presenti in programmi sequenziali, non è stato implementato alcun
metodo di trasformazione automatico, tranne in alcuni casi ben definiti, in cui l’ordine
della sequenza di trasformazioni ristrutturanti da applicare sia dimostrabile garantire
un reale miglioramento delle prestazioni.
Il problema di individuare la migliore sequenza di trasformazioni, noto col nome di
phase ordering [EH00]; è molto complesso, ed una possibile soluzione euristica
consiste, in fase di sviluppo del compilatore, nel verificare, su parti di codice di cui
non è nota a priori la sequenza ottimale di trasformazioni, differenti sequenze di
trasformazioni ristrutturanti, e quindi di misurare quale sequenza produce il codice
con prestazioni migliori.
Oggetto di questo lavoro di tesi è lo studio e l’implementazione (prototipazione) di un
ambiente di programmazione per lo sviluppo di un compilatore fortemente modulare
in cui le componenti di analisi e di ristrutturazione del codice possono essere
combinate e ricombinate per ottenere da un lato maggiore flessibilità di utilizzo e
dall’altro codici con migliori prestazioni computazionali. In particolare l’ambiente
sviluppato si caratterizza per la semplicità di utilizzo. E’ possibile la codifica ed il test
di algoritmi per l’analisi e trasformazione del codice, in maniera semplice ed
efficiente. Questo vincolo progettuale ha fornito criteri per la scelta del linguaggio di
programmazione con cui implementare un ambiente di sviluppo di compilatori con
queste caratteristiche. L’attenzione si è infatti rivolta verso i linguaggi di
manipolazione simbolica ed in particolare verso il più rappresentativo di questi, il
LISP [McCar60]. Esso possiede caratteristiche uniche che lo rendono lo strumento
più idoneo per la programmazione e la manipolazione simbolica di strutture dati ed
algoritmi. L’aspetto più significativo è il fatto che le funzioni, con cui sono descritti
tutti i processi di calcolo, possono esse rappresentate nelle stesse strutture dati del
LISP. Questo distingue la programmazione in LISP dagli altri paradigmi di
programmazione, poiché questi ultimi si fondano sulla tradizionale dicotomia tra dato
ed algoritmo. Questa funzionalità rende quindi il LISP lo strumento migliore, per la
INTRODUZIONE
10
scrittura di programmi che manipolano altri programmi come dati, come ad esempio
gli interpreti ed infine proprio i compilatori [AS85].
Il prototipo implementato risulta costituito da tre componenti fondamentali:
1. Il Front-End per il linguaggio Fortran del compilatore parallelizzante
Parafrase2.
2. Un Modulo di Conversione la cui funzione è la trasformazione della
rappresentazione intermedia costruita dal front-end del compilatore
parallelizzante Parafrase2 in un formato leggibile e manipolabile dal linguaggio
LISP.
3. Una libreria di funzioni LISP per l’analisi del codice (Analisi del Flusso e
Analisi delle Dipendenze).
Elemento caratterizzante del prototipo è che l’ambiente di compilazione e di sviluppo
è costituito per intero dal sistema LISP. E’ infatti possibile compilare codice Fortran
ed ottenere la relativa rappresentazione intermedia in formato LISP, pur rimanendo
nel sistema. Questo è stato possibile attraverso l’implementazione di una funzione
LISP (fortran_front_end) in cui sono integrati i primi due elementi del prototipo,
rispettivamente il Front-End di Parafrase2 ed il Modulo di Conversione.
Il lavoro di Tesi è organizzato come segue.
Nel Capitolo 1, dopo una breve panoramica di carattere generale sui linguaggi di
programmazione, viene data una definizione formale di cosa sia un programma c,
scritto in un linguaggio di programmazione, _. In seguito sono introdotte le strutture
dati utilizzate per la rappresentazione di un programma: l’albero sintattico, la tabella
simboli ed il grafo di flusso del controllo. Muniti di queste strutture viene fornita la
definizione di esecuzione sequenziale di un programma e presentato l’algoritmo di
esecuzione. Infine viene introdotto il paradigma di programmazione simbolico, e
descritto il linguaggio di programmazione LISP. Nel Capitolo 2 è introdotta l’Analisi
di Flusso di un Programma. In ordine cronologico, è il primo tipo di analisi del
codice, effettuato dal compilatore. L’Analisi del Flusso del Programma si suddivide
nella Analisi del Flusso di Controllo, utile per la ricerca di costrutti iterativi
INTRODUZIONE
11
all’interno del codice, che sono i maggiori candidati alla parallelizzazione, ed in
Analisi del Flusso dei Dati, che si occupa della raccolta di informazioni sull’uso delle
variabili nel programma. Questa tecnica di analisi è anche utilizzata nella fase di
ottimizzazione del codice per elaboratori di tipo seriale. Il Capitolo 3 ha per oggetto
l’Analisi di Dipendenza Dati. Questa tecnica di analisi consente di determinare se due
o più istruzioni differenti referenziano una stessa locazione di memoria (dipendenza
dati). Se questo non accade allora è possibile assegnare ciascun frammento di codice
indipendente ad un flusso di controllo diverso, cioè è possibile eseguire questi
frammenti in contesti di esecuzione concorrenti. Sono esposti i concetti fondamentali,
in particolare per caratterizzare la dipendenza dati nei costrutti iterativi. È infine
descritto il Greatest Common Divisor test per la dipendenza dati la cui
implementazione è descritta nel Capitolo 10. Il Capitolo 4 descrive le principali
tecniche di ristrutturazione per lo sfruttamento di euristiche di ottimizzazione. Il
Capitolo 5 descrive le principali tecniche di ristrutturazione dei costrutti ciclici. Nel
Capitolo 6 vengono esposte le principali problematiche legate alla tecniche di
programmazione e compilazione di macchine parallele. La definizione di esecuzione
di un programma viene estesa al caso di un ambiente di calcolo parallelo, è quindi
fornito un modello minimale per un ambiente di esecuzione parallelo. In questo
contesto è schematizzato l’algoritmo di esecuzione parallela di un programma c. Il
capitolo termina con la descrizione delle principali funzionalità dei compilatori. Il
processo di compilazione è suddiviso in una serie di sottoprocessi chiamati fasi. Dopo
le fasi di analisi (lessicale, sintattica, semantica) il compilatore genera un
Rappresentazione Intermedia del codice sorgente, ad uso delle successive fasi del
processo di compilazione. Nel Capitolo 7 è introdotto il compilatore parallelizzante
Parafrase2, in particolare sono descritte le strutture dati interne utilizzate dal
compilatore per la costruzione dell’Albero Sintattico e della Tabella Simboli che
insieme definiscono la Rappresentazione Intermedia del programma. Il Capitolo 8 ha
per oggetto la descrizione della procedura di lavoro adottata per la implementazione
del Modulo di Conversione. Inizialmente il Modulo, scritto in linguaggio C, è stato
INTRODUZIONE
12
inserito come passo di compilazione nel compilatore Parafrase2 e quindi
opportunamente verificato. In una seconda fase, si è provveduto a costruire una
interfaccia tra il front end di Parafrase2, con annesso Modulo di Conversione, con
l’ambiente di programmazione LISP utilizzato (l’XLISP). Il risultato ottenuto è la
costruzione di una nuova primitiva LISP: (fortran_front_end), che consente di
utilizzare il front-end di Parafrase2 con annesso Modulo di Conversione in ambiente
LISP. Il capitolo termina con esempi di applicazione della funzione che mostrano
come è strutturata la rappresentazione intermedia ottenuta. Nel Capitolo 9 sono
riportati gli algoritmi e le funzioni LISP con cui è implementata l’Analisi di Flusso
del Programma. Per l’Analisi del Flusso di Controllo sono state implementate
funzioni LISP per la costruzione e la rappresentazione grafica del Grafo di Flusso del
Controllo (Control Flow Graph) con cui sono rappresentati i potenziali cammini di
esecuzione del programma. Su questa struttura è stato possibile, in una fase
successiva, implementare delle funzioni LISP per la individuazione dei costrutti
iterativi all’interno del CFG (Componenti connesse e Dominatori). Inoltre sono state
implementate delle funzioni LISP per la costruzione del Grafo delle Dipendenze Dal
Controllo (Postdominatori). Per l’Analisi del Flusso dei Dati sono state implementate
funzioni LISP per la soluzione dei principali problemi di analisi data flow definiti nel
Capitolo 2. Il capitolo termina con la descrizione di alcuni esempi di applicazione
delle funzioni implementate.
Infine nel Capitolo 10 è descritta la procedura di lavoro e gli algoritmi utilizzati per
l’implementazione del test per la dipendenza dati. La codifica degli algoritmi per il
test ha richiesto, per motivi di efficienza la costruzione in linguaggio C, delle
procedure che calcolano, rispettivamente, la riduzione a gradino e la risoluzione di
sistemi di equazioni diofantee. In seguito si è provveduto a costruire una interfaccia
tra il codice implementato e le strutture dati interne dell’ambiente di programmazione
XLISP. Si sono così ottenute due nuove primitive al linguaggio LISP : (echelon)
e (diophantine). E’ quindi descritta la funzione LISP (test-dipendenza)
che consente di impostare il sistema di equazioni diofanteee per il calcolo della
INTRODUZIONE
13
dipendenza dati. Sono riportati gli algoritmi utilizzati per il test e descritte le
principali funzioni LISP implementate. Il capitolo termina con la descrizione di alcuni
esempi di applicazione del test e della implementazione di una tecnica di
trasformazione di costrutti ciclici nota come loop interchanging, che fa uso del test di
dipendenza implementato, anche in questo caso sono riportate le funzioni LISP
definite e descritto un esempio di applicazione.
CAPITOLO 1 – MODELLI COMPUTAZIONALI DEI PiU’ COMUNI PARADIGMI DI PROGRAMMAZIONE
14
Capitolo 1 - Modelli Computazionali dei
più comuni paradigmi di programmazione
1.1 - Linguaggi di Programmazione
Un linguaggio di programmazione _ deve essere inteso come un linguaggio, nel
senso delle teorie linguistiche, la cui caratteristica principale è quella di generare
azioni su un qualche sistema di calcolo. Da questo punto di vista, un linguaggio di
programmazione è caratterizzato da:
1) una sintassi, che ne descrive la struttura linguistica, delimitando le frasi ben
formate mediante, ad esempio, una grammatica;
2) una semantica, che correla le frasi ben formate del linguaggio alle azioni del
sistema di calcolo; ed infine,
3) una pragmatica, il cui ruolo principale è quello di armonizzare la sintassi e
semantica del linguaggio di programmazione con le limitazioni della teoria
della computazione e del sistema di calcolo con l’utilizzo concreto del
linguaggio.
Ad un linguaggio _ di programmazione è associata una grammatica G
_
che consente
di verificare se un programma c, scritto nel linguaggio _, è costituito da frasi ben
formate. Questo in generale è effettuato in modo automatico nel senso che, per alcune
classi di grammatiche, è possibile scrivere un programma, detto parser, che riceve in
ingresso il programma c scritto nel linguaggio _ e verifica, in un tempo finito, la
correttezza di c rispetto al linguaggio _.
L’insieme delle frasi ben formate può essere partizionato in classi sintattiche che, in
generale disgiunte, catturano le funzionalità di base di un linguaggio di
CAPITOLO 1 – MODELLI COMPUTAZIONALI DEI PiU’ COMUNI PARADIGMI DI PROGRAMMAZIONE
15
programmazione consentendo di realizzare un ponte verso la semantica dello stesso
linguaggio. Le classi più utilizzate sono: la classe delle frasi dichiarative, e la classe
delle frasi imperative. Dove le frasi dichiarative sono utilizzate, dal compilatore e dal
Run Time Language (RTL) per allocare le strutture dati di un programma, mentre le
frasi imperative sono utilizzate per catturare e modificare, ad ogni istante, lo stato
della computazione associata al programma. In generale la struttura di
rappresentazione dello stato di una generica computazione è:
X , V
i
⊥
i 0
k
dove X è l’ambiente della computazione, e
V
i
⊥
i 0
k
sono le continuazioni associate
alla frase ben formata di tipo imperativa. In generale k=0, cioè vi è una sola
continuazione, nel caso di istruzione di controllo saranno presenti più di una
continuazione. Ad esempio nel caso del costrutto:
if condizione then istruzione
1
else istruzione
2
saranno presenti due continuazioni, la prima relativa al ramo then e la seconda al
ramo else.
Per definire la semantica di un linguaggio di programmazione _ è necessario
individuare l’insieme b degli oggetti su cui il linguaggio opererà. All’interno di un
linguaggio di programmazione è resa disponibile la nozione di variabile, nozione
caratterizzata da proprietà che dipendono dal linguaggio di programmazione in uso.
Tra le più importanti proprietà vanno sicuramente citate:
ƒ il nome dell’oggetto, cioè una stringa di caratteri con cui individuare
univocamente l’oggetto denotato
1
;
ƒ Un insieme di attributi, che specifica i vincoli che dovrà verificare il valore di
una variabile. Tra questi oltre al tipo, che specifica l’insieme dei valori che la
1
Si osservi che tale stringa può essere resa sia pubblica, nel senso che l’utente può riferirsi ad essa,
sia invisibile, nel senso che solo il sistema di RTL può riferirsi, nel qual caso si dirà che l’oggetto è
anonimo.
CAPITOLO 1 – MODELLI COMPUTAZIONALI DEI PiU’ COMUNI PARADIGMI DI PROGRAMMAZIONE
16
variabile può assumere, sono presenti quello relativo alla visibilità della
variabile, cioè la regione di programma in cui è attivo l’insieme degli attributi,
e l’estensione della variabile, cioè l’intervallo di tempo durante l’esecuzione
di un programma, nel quale è attivo l’insieme degli atributi.
ƒ Il riferimento, che indica l’area di registrazione dove il valore della variabile
verrà conservato.
Un tipo di dati è rappresentato dalla coppia costituita da una collezione di oggetti (il
dominio) ed una collezione di operazioni definito sugli oggetti atte a creare, costruire,
distruggere, modificare e raccogliere le istanze degli oggetti.
Si dice che un tipo di dati è scalare se il suo dominio è costituito unicamente da valori
semplici. Esempi di dati scalari sono gli interi, reali, booleani e cararatteri, cioè tipi
elementari di dati. Contrapposti ai tipi scalari si possono definire i tipi strutturati, per i
quali il dominio consiste di elementi che sono essi stessi composti da un insieme di
tipi. Questo implica che gli elementi di un tipo strutturato sono costruiti a partire da
elementi che a loro volta possono avere tipi propri.
Esempi di dati strutturati sono gli array ed i record. Dove un array è un aggregato di
elementi omogenei di dati identificati dalla loro posizione all’interno dell’aggregato, e
caratterizzati da un nome, da una lista di dimensioni, da un tipo per i propri elementi e
da un tipo ed un dominio per i valori dei propri indici. Un record è un aggregato di
elementi (generalmente) eterogenei identificati da un nome sia per l’intero aggregato
che per gli elementi.
Nella semantica dei linguaggi di programmazione il termine ambiente si riferisce alla
funzione che associa ad ogni nome una locazione di memoria, mentre con il termine
stato indica la funzione che associa ad una locazione di memoria il valore registrato:
valorememorianome
statoambiente
ο ο
Il legame tra la sintassi di un linguaggio di programmazione _ e la corrispondente
semantica è generalmente ottenuta associando ad ogni elemento descrittivo della
sintassi, più in particolare ad ogni regola della grammatica, una funzione che associa
CAPITOLO 1 – MODELLI COMPUTAZIONALI DEI PiU’ COMUNI PARADIGMI DI PROGRAMMAZIONE
17
le regole di trattamento degli oggetti 2. Questa fase del processo di definizione di un
linguaggio di programmazione _ è parzialmente automatizzabile, ed in generale si
utilizza un meccanismo del tipo pattern-matching, cioè si esprimono le regole della
grammatica G
_
mediante patterns che debbono essere controllati sulla
rappresentazione simbolica di ingresso del programma, nel caso in cui un pattern è
verificato viene avviata l’esecuzione della corrispondente azione. Dove l’azione
implementerà il vincolo espresso dalla semantica che dalla pragmatica del linguaggio
di programmazione in considerazione. Da quanto detto è evidente che alcuni aspetti
della semantica possono essere direttamente implementati e verificati durante la fase
di analisi sintattica del programma c espresso in un linguaggio di programmazione
_.
Vi sono tuttavia alcuni aspetti della semantica e della pragmatica del linguaggio di
programmazione _ che debbono essere trattati in una fase separata, indicata con
definizione del Run Time Language. In essa sono confinati tutti quegli aspetti
necessari alla corretta esecuzione di un programma c espresso nel linguaggio di
programmazione _. In altre parole nello RTL vengono affrontati tutti i problemi
relativi al modello di esecuzione soggiacente un linguaggio di programmazione, quali
ad esempio il meccanismo di passaggio dei parametri fra l’invocazione di una
procedura rispetto alla sua definizione, la gestione delle strutture dati a visibilità non
globale, la gestione delle informazioni di controllo, la gestione della disciplina di
gestione dello stack, e così via. In definitiva possiamo dire che la definizione di un
sistema che accetti un programma espresso in un linguaggio di programmazione e che
lo possa eseguire è costituito dalle seguenti componenti software:
1) un parser, che riconosce se la rappresentazione in ingresso del programma
scritto nel linguaggio di programmazione _ è ben formata, cioè priva di errori;
2) un programma che effettua la conversione del programma c in un altro
linguaggio più semplice da eseguire su un dato sistema di calcolo;
CAPITOLO 1 – MODELLI COMPUTAZIONALI DEI PiU’ COMUNI PARADIGMI DI PROGRAMMAZIONE
18
3) un ambiente di esecuzione (RTL) che completi l’ambiente disponibile sul
sistema di calcolo con l’ambiente di esecuzione sotteso al linguaggio di
programmazione _.
È ovvio che affinché queste componenti software possano cooperare tra loro
nell’esecuzione del programma c è necessario che si scambino delle informazioni, a
questo scopo è necessario definire opportune rappresentazioni intermedie dei
programmi (Intermediate Program Representation - IPR). In definitiva si ha che lo
scenario sottostante la progettazione ed esecuzione di un programma espresso in un
linguaggio di programmazione _ è quello mostrato in Figura 1-1.
Ambiente di
esecuzione
RTL
Parser
Figura 1-1 : Scenario sottostante l’esecuzione di un programma
I due elementi fondamentali che legano le istruzioni tra loro sono: il passaggio del
controllo, ed il flusso dei dati. Assegnato un linguaggio di programmazione _
possiamo adottare la seguente definizione di programma:
Definizione 1.1
Un programma, scritto nel linguaggio di programmazione _, è rappresentato dalla
tripla
S
i
⊥
i 1
n
,p
s
, 3
I / O
dove:
1) S
i
⊥
i 1
n
è l’insieme delle istruzioni in cui ciascuna delle
S
i
_ ;
CAPITOLO 1 – MODELLI COMPUTAZIONALI DEI PiU’ COMUNI PARADIGMI DI PROGRAMMAZIONE
19
2)
p
s
è la relazione d’ordine parziale su S
i
⊥
i 1
n
e cattura l’ordine di
esecuzione del programma, compatibile con la semantica di _, per ogni insieme
di dati di ingresso di c;
3) 3
I / O
è l’insieme delle proprietà di input/output che debbono essere
verificate in ogni esecuzione di c.
Allora si dovrà trovare una struttura dati per la rappresentazione del programma c
tale da consentire, allo stesso tempo, di catturare la rappresentazione di S
i
⊥
i 1
n
e la
relazione
p
s
. È ovvio che i candidati migliori sono le strutture dati ottenute a partire
dai grafi. Più in particolare avremo che le seguenti strutture dati sono utilizzate per la
comunicazione tra le varie componenti dell’ambiente di esecuzione di un programma:
ƒ l’Albero Sintattico Astratto (Abstract Syntax Tree - AST) è prodotto in uscita
dal parser e fornisce la struttura ad albero utilizzata durante la fase di
riconoscimento di frase ben formata rispetto al linguaggio di programmazione
_.
ƒ la Tabella dei Simboli (Symbol Table - ST) dove sono registrate tutte le
informazioni sui nomi degli oggetti che si dovranno utilizzare nell’esecuzione
del programma.
Da queste strutture dati è estratta la struttura dati che rende esplicita la relazione
d’ordine delle possibili esecuzioni di un programma, cioè si estrae il passaggio del
flusso di controllo tra le istruzioni. Questa struttura dati indicata con il nome di Grafo
del Flusso di Controllo (Control Flow Graph - CFG), può essere così rappresentata:
CFG = (N, E, Start) dove N è l’insieme dei nodi in cui si articola il controllo, E
l’insieme degli archi connettenti due nodi correlati tra loro dal passaggio potenziale
del flusso di controllo, ed Start è il nodo da cui si avvia il controllo dell’intero
programma, indicato in generale con il nome di nodo di start.
Più in particolare abbiamo che per un dato programma c =
S
i
⊥
i 1
n
,p
s
, 3
I / O
e
l’associato CFG, dovremo avere che l’in-degree e/o l’out-degree di almeno un nodo
CAPITOLO 1 – MODELLI COMPUTAZIONALI DEI PiU’ COMUNI PARADIGMI DI PROGRAMMAZIONE
20
x
i
N deve essere differente da 1, altrimenti l’intero programma si può ridurre ad un
solo nodo. Inoltre, se esiste un nodo con in-degree(x
i
) ≥ 1 allora dovrà esistere almeno
un nodo con out-degree(x
j
) ≥ 1, in altre parole dovrà esistere almeno un’istruzione di
diramazione nel programma c.
Si osservi che, in generale, ogni nodo del CFG, a cui è dato il nome di basic block
2
, è
annotato con informazioni pertinenti il trattamento che il nodo stesso dovrà subire
durante l’esecuzione del programma da cui è derivato. In questo contesto avremo che
per un dato programma c =
S
i
⊥
i 1
n
,p
s
, 3
I / O
e l’associato CFG, ogni cammino
in CFG x
1
, }, x
n
, con x
1
= i (nodo di avvio - Start), x
n
= Stop (nodo di terminazione -
Stop) ed x
i
N è detto essere un’esecuzione sequenziale X
s
di c.
Ad ogni nodo del CFG si associano delle annotazioni indicate con Entry_Block(x
i
),
Exit_Block(x
i
) e Code_Block(x
i
) che debbono rispettivamente essere valutate
prima e/o dopo l’esecuzione del nodo stesso, e Code_Block è il codice che deve
essere seguito per l’esecuzione del nodo x
i
. Le informazioni presenti, rispettivamente,
in Entry_Block ed Exit_Block sono riassunte nella seguente tabella:
In generale l’algoritmo di esecuzione di un programma così rappresentato può essere
schematizzato in:
2
La definizione di basic block è data nel Capitolo 2
ENTRY Block EXIT Block
Operazioni indipendenti dal Basic Block:
1) Allocazione di variabili private del nodo x
i
e
dello stack del programma
1) Propagazione delle informazioni per le
clausole condizionali
2) Scelta del nodo successi da eseguire
Operazioni dipendenti dal Basic Block
1) Esecuzione del codice di inizializzazione,
ove esistente
1) Aggiornamento dei contesti computazionali;
2) Sincronizzazione con le richieste al Sistema
Operativo
CAPITOLO 1 – MODELLI COMPUTAZIONALI DEI PiU’ COMUNI PARADIGMI DI PROGRAMMAZIONE
21
push (START) ;
while (~ empty_stack ()) {
x
i
= pop () ;
evaluate (Entry_Block (x
i
)) ;
execute (Code_Block (x
i
)) ;
evaluate (Exit_Block (x
i
)) ;
push (branch (x
i
)) ;
}
Dalle precedenti definizioni abbiamo che una esecuzione sequenziale X
s
di un
programma c codificato in un linguaggio di programmazione _ è dato da uno dei
possibili cammini che vanno dal nodo Start al nodo Stop sul grafo di controllo, la cui
scelta concreta dipende dai dati di ingresso del programma c. Dal punto di vista
dell’implementazione, assegnato un programma c, scritto in un linguaggio di
programmazione _, esso può essere eseguito in due modalità:
1) la modalità interpretata, dove l’intero ambiente di esecuzione è realizzato da
un unico programma, detto interprete del linguaggio _, e
2) la modalità compilata, dove l’ambiente di esecuzione è suddiviso in più
componenti indipendenti.
Più in particolare si avrà che il compilatore, tradurrà il programma c dal linguaggio di
programmazione _ in un programma equivalente che opportunamente trattato dal
link-editor ed in combinazione con le librerie che implementano il RTL potrà essere
eseguito. In generale queste due modalità si differenziano per i tempi di sviluppo ed i
tempi di esecuzione del programma. È evidente che i tempi di sviluppo di un
programma nella modalità interpretata sono significativamente più bassi rispetto alla
modalità compilata. Mentre, per quanto riguarda i tempi di esecuzione di un
programma la modalità interpretata presenta, in generale, tempi di esecuzione
maggiori della modalità compilata.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.