Università degli Studi di Udine
Facoltà di Scienze Matematiche Fisiche e Naturali
Corso di Laurea Triennale in Informatica
Tesi di Laurea
Implementazione distribuita del
linguaggio Pascal
Candidato:
Relatore:
Matteo Cicuttin
Prof. Marco Comini
Anno Accademico 2006/2007
Università degli Studi di Udine
Via delle Scienze, 206
33100 Udine
Italia
A tutti quelli che hanno fatto in modo che arrivassi fino a qui, in particolare alla
mia famiglia, che mi ha dato ogni supporto, incondizionatamente.
A tutti quelli che in qualche modo mi hanno ostacolato o non hanno creduto in
questa mia impresa, che mi hanno dato un’occasione per crescere ed imparare a
muovermi da solo.
Ringraziamenti
I miei più sentiti ringraziamenti vanno a tutti coloro che mi sono stati vicini durante
questi anni di università, a tutta l’ASCI che ha sopportato la mia politica di rete
“default deny”, in particolare all’ultimo direttivo di cui ho fatto parte e a Beppe,
che ha sopperito alle mie “mancanze” dal ruolo di presidente durante questo ultimo
anno in cui sono stato veramente carico al 100%.
Grazie alla combriccola del Tomadini, ovvero Attila, Baba grande, Baba piccolo,
Mio e Samuele per il fantastico anno passato in quel luogo altrimenti, dal punto di
vista persone, pessimo.
Grazie a Jimmy, che ha sopportato le mie divagazioni durante i momenti di studio
che avrebbero dovuto essere seri.
Sono in debito con tutti i miei professori dell’ITIS Da Vinci di Portogruaro,
per la solida preparazione che mi hanno dato. Grazie a loro ho potuto “vivere di
rendita” in parecchie occasioni all’università. Continuate cosi! Un grazie particolare
va ai miei insegnanti di matematica: alla Prof.ssa Volcan che ha messo le basi per
permettermi di “fare pace” con questa disciplina. Nonostante il mio 4 fisso, ha
creduto in me e ha visto oltre al voto. A Paolo, che ha avuto la capacità di farmi
vedere il lato divertente dei numeri anche se non mi volevano entrare in testa. Al
Prof. Rizzetto, che mi ha trasmesso il fascino e la perfezione della matematica, e
che con il 9 in quinta mi ha convinto che era alla mia portata. L’informatica è
qualcosa di molto diverso da un semplice computer: l’informatica vera è fatta di
teoremi e dimostrazioni ed impone un certo rigore matematico. È grazie a loro che
sono riuscito ad entrare nell’ottica giusta e a laurearmi in questa disciplina e spero
che questo mio risultato possa essere per tutti loro una piccola ricompensa per la
fiducia che hanno riposto in me.
Elaborare questa tesi è stato un compito non difficile, ma decisamente molto
impegnativo, infatti il rapporto
ragionamento
righe di codice
è stato per me abbastanza alto. Tut-
tavia, questo lavoro mi ha migliorato, e non di poco. Mi ha innanzitutto permesso
di esplorare il campo dei compilatori: prima di accettare questa tesi, per me essi
erano qualcosa di simile alla magia nera, e non avrei mai creduto che sarei riuscito a
scriverne uno, traendone tra l’altro notevole soddisfazione. Durante la costruzione
di questo sistema sono andato diverse volte “off topic”. Se da un lato ciò mi ha fatto
perdere tempo, dall’altro ho avuto modo di imparare moltissimo sui compilatori.
Un lavoro come questo, che sfiora le 10000 righe di codice (senza considerare tutto il
codice che è finito in /dev/null), inoltre mi ha permesso di rendermi conto almeno
un po’ di cosa significhi programmare “in grande” e di quanto sia importante in ogni
caso progettare per bene prima di “fare”. Mi ha anche fatto capire che è assolutamente necessario che, finito questo lavoro, mi metta a studiare come progettare
ad oggetti. Infine, ho imparato (in parte) LATEX. Se avessi dovuto scrivere questa
tesi con il famoso word processor di $(una_software_house_a_caso), sarebbe stata
una tragedia.
In breve, ora mi sento una persona diversa ed il mio grazie va a tutti coloro che
hanno fatto si che questo succedesse.
La presente tesi è stata prodotta utilizzando esclusivamente software open source. L’ambiente LATEXutilizzato è TeXShop. Per la grafica vettoriale è stato utilizzato
InkScape. Per i grafi è stato utilizzato GraphViz.
La comunità che ruota attorno all’open source ci offre del software ottimo senza
chiederci alcunché in cambio: per questo motivo tutto il lavoro svolto è disponibile all’indirizzo http://sourceforge.net/projects/opc, nella speranza che, come i tre
software che ho citato mi sono stati utili nell’elaborarlo, anche tutto questo lo sia a
qualcuno.
Indice
1 Introduzione
1.1
1.2
Descrizione generale del sistema . . . . . . . . . . . . . . . . . . . . .
2
1.1.1
L’ambiente runtime . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2
Il compilatore . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Organizzazione del lavoro . . . . . . . . . . . . . . . . . . . . . . . .
5
2 Panoramica sulle architetture parallele e distribuite
2.1
2.2
2.3
7
Parallelismo fine-grained . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1.1
Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1.2
Processori vettoriali . . . . . . . . . . . . . . . . . . . . . . .
8
Parallelismo coarse-grained . . . . . . . . . . . . . . . . . . . . . . .
9
2.2.1
Architetture a memoria condivisa . . . . . . . . . . . . . . . .
10
2.2.2
Architetture a memoria distribuita . . . . . . . . . . . . . . .
10
Programmazione delle macchine a memoria distribuita con MPI . . .
11
2.3.1
Concetti alla base di MPI . . . . . . . . . . . . . . . . . . . .
12
2.3.2
Esempio di utilizzo: Integrazione numerica con MPI . . . . .
13
2.3.3
Compilazione ed utilizzo del software in ambiente MPI . . . .
15
3 P-Code e P-Machine
3.1
1
17
I registri della P-Machine . . . . . . . . . . . . . . . . . . . . . . . .
18
3.1.1
PC - Il program counter . . . . . . . . . . . . . . . . . . . . .
18
3.1.2
SP - Stack Pointer . . . . . . . . . . . . . . . . . . . . . . . .
18
3.1.3
MP - Mark Stack Pointer . . . . . . . . . . . . . . . . . . . .
19
3.2
Istruzioni aritmetico/logiche . . . . . . . . . . . . . . . . . . . . . . .
19
3.3
Istruzioni di LOAD/STORE . . . . . . . . . . . . . . . . . . . . . . .
20
3.3.1
LDA - Load Address . . . . . . . . . . . . . . . . . . . . . . .
21
3.3.2
LDI - Load Immediate . . . . . . . . . . . . . . . . . . . . . .
23
3.3.3
LDC - Load Constant . . . . . . . . . . . . . . . . . . . . . .
23
ii
Indice
3.3.4
LOD - Load Indirect . . . . . . . . . . . . . . . . . . . . . . .
23
3.3.5
STO - Store . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.4
Istruzioni di accesso con indice . . . . . . . . . . . . . . . . . . . . .
24
3.5
Istruzioni di salto e di confronto
. . . . . . . . . . . . . . . . . . . .
25
3.5.1
UJP - Unconditional Jump . . . . . . . . . . . . . . . . . . .
25
3.5.2
FJP - Jump On False . . . . . . . . . . . . . . . . . . . . . .
25
Istruzioni relative alle chiamate . . . . . . . . . . . . . . . . . . . . .
26
3.6.1
Istruzioni relative al chiamante . . . . . . . . . . . . . . . . .
26
3.6.2
Istruzioni relative al chiamato . . . . . . . . . . . . . . . . . .
28
3.6
4 Architettura del compilatore
4.1
29
Introduzione al concetto di linguaggio formale . . . . . . . . . . . . .
30
4.1.1
Linguaggi regolari . . . . . . . . . . . . . . . . . . . . . . . .
30
4.1.2
Linguaggi context-free . . . . . . . . . . . . . . . . . . . . . .
31
Analisi Lessicale e Sintattica . . . . . . . . . . . . . . . . . . . . . . .
33
4.2.1
Lo scanner . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2.2
Il parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.3
Analisi semantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
4.4
Determinazione del tipo delle espressioni . . . . . . . . . . . . . . . .
39
4.5
La tabella dei simboli . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.6
Generazione del codice . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.7
Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
4.2
5 Tecniche di analisi volte alla parallelizzazione automatica
5.1
5.2
45
Analisi delle dipendenze . . . . . . . . . . . . . . . . . . . . . . . . .
45
5.1.1
Dipendenze sui dati . . . . . . . . . . . . . . . . . . . . . . .
45
5.1.2
Dipendenze sui cicli . . . . . . . . . . . . . . . . . . . . . . .
48
5.1.3
Dipendenze sul controllo . . . . . . . . . . . . . . . . . . . . .
48
Analisi dei dati utilizzati dal codice . . . . . . . . . . . . . . . . . . .
49
5.2.1
49
Condizioni di Bernstein . . . . . . . . . . . . . . . . . . . . .
6 Descrizione del lavoro svolto
53
6.1
Idea generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
6.2
Modifiche al compilatore . . . . . . . . . . . . . . . . . . . . . . . . .
55
Indice
6.3
iii
6.2.1
Le relazioni uses e usedby . . . . . . . . . . . . . . . . . . . .
55
6.2.2
Operazione di join . . . . . . . . . . . . . . . . . . . . . . . .
58
6.2.3
Numerazione delle funzioni . . . . . . . . . . . . . . . . . . .
59
6.2.4
Numerazione delle variabili ed allocazione . . . . . . . . . . .
60
Modifiche all’ambiente runtime . . . . . . . . . . . . . . . . . . . . .
62
6.3.1
Istruzione WAIT . . . . . . . . . . . . . . . . . . . . . . . . .
63
6.3.2
Istruzione CUP . . . . . . . . . . . . . . . . . . . . . . . . . .
64
6.3.3
Istruzione RET . . . . . . . . . . . . . . . . . . . . . . . . . .
65
Conclusioni
67
Bibliografia
69
iv
Indice
Elenco delle figure
1.1
Albero di sintassi astratta . . . . . . . . . . . . . . . . . . . . . . . .
4
2.1
Multiprocessore a memoria condivisa . . . . . . . . . . . . . . . . . .
10
2.2
Macchina a memoria distribuita . . . . . . . . . . . . . . . . . . . . .
11
3.1
Struttura a livelli del linguaggio Pascal . . . . . . . . . . . . . . . . .
18
3.2
Collocazione di un array in memoria . . . . . . . . . . . . . . . . . .
24
3.3
Stack frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.1
Albero di sintassi astratta . . . . . . . . . . . . . . . . . . . . . . . .
35
4.2
Albero di sintassi astratta completo di informazione di tipo . . . . .
40
4.3
Tabella dei simboli . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.4
Albero per l’espressione T rue or F alse and T rue . . . . . . . . . . .
42
6.1
Esempio di programma che contiene funzioni separabili . . . . . . . .
54
6.2
Programma con cluster non banali . . . . . . . . . . . . . . . . . . .
56
6.3
Albero con le informazioni relative ai cluster . . . . . . . . . . . . . .
59
vi
Elenco delle figure
1
Introduzione
Quando negli anni ’40 nacquero i primi calcolatori elettronici, mai si sarebbe immaginato un loro cosı̀ massiccio e pesante impiego come quello che possiamo osservare
ai giorni nostri. Oggi, pur non pensandoci, siamo continuamente assistiti da diversi
computer, da quelli di scala più ridotta, come l’orologio digitale che indossiamo, a
quelli di classe server con i quali interagiamo ad esempio durante la navigazione in
Internet. La loro flessibilità ci porta a chiedere a queste macchine di automatizzare
sempre più operazioni quotidiane e offrire sempre più servizi. Nell’ambito scientifico
i computer sono di primaria importanza nelle simulazioni e in altre applicazioni che
richiedano enormi moli di calcoli. Il sempre crescente carico di lavoro che imponiamo alle macchine ha richiesto un continuo sviluppo dell’hardware, fino ad arrivare
ai sistemi SMP (Simmetrical Multi Processor) e più recentemente SMT (Simultaneous Multi Threading) e CMP (Chip-level Multi Processor). Se i primi non hanno
conosciuto una grande diffusione sotto alla scrivania dell’utente generico, gli SMT
e i CMP stanno acquistando sempre maggiore diffusione a causa del loro basso costo. Il trend di sviluppo dell’hardware di calcolo si sta orientando sempre più verso
queste architetture. Intel, maggiore produttore al mondo di microprocessori, ha un
prototipo di CPU ad 80 nuclei, mentre Sun Microsystems nel 2005 ha presentato
il chip Niagara, conosciuto anche come UltraSPARC T1. Questo chip esiste nelle
versioni da 4, 6 e 8 core, capace di eseguire 4 thread simultaneamente per ogni core.
Recentemente è stata presentata la versione T2, di capacità altamente superiori al
precedente T1. Anche IBM ha presentato un chip parallelo, però sostanzialmente
diverso dagli Intel Core e dagli UltraSPARC T1. Il chip in questione è CELL. Esso
è caratterizzato da un core basato su architettura Power, ed affiancato da 8 unità
specializzate in task di carattere multimediale, connesse tra loro ad altissima velocità. Un tale grado di parallelismo a livello di hardware richiede che il software sia
scritto secondo certi criteri, che mirino al massimo sfruttamento di questo tipo di
2
1. Introduzione
architetture. Purtroppo è il programmatore ad avere l’arduo compito di capire come
scrivere al meglio il software per sfruttare questo massiccio parallelismo. Esistono
numerosi tool e librerie che vengono in aiuto, basti pensare a MPI, PVM, MOSIX.
Il risultato rimane comunque qualcosa di “fatto a mano”.
Diversi lavori sono stati fatti nella direzione della parallelizzazione automatica:
IBM sta lavorando ad un compilatore sperimentale, Octopiler, per ottenere binari
“paralleli” da eseguire su CELL. Dai report di IBM si può vedere che con l’aiuto del
compilatore si possono ottenere incrementi di performance in alcuni casi anche di
20 volte. Anche la Stanford University ha sviluppato un compilatore parallelizzante
di livello molto avanzato, SUIF, non per CELL ma general-purpose.
Questa tesi si pone come obiettivo l’esplorazione di alcune tecniche volte a cercare il parallelismo all’interno del codice di un programma, e alla compilazione di
tale codice in un formato adatto all’esecuzione su più unità di calcolo di una macchina a memoria distribuita, svincolando in parte il programmatore dal compito di
parallelizzare manualmente il codice. L’idea che ha guidato l’implementazione di
questo sistema è che in un software generalmente esistono sezioni di codice che non
condividono dati. Tali sezioni di codice, previa la creazione di un ambiente adatto,
possono essere fatte eseguire su una macchina diversa da quella in cui il programma
è stato lanciato. Per tali sezioni di codice viene generata dal compilatore una chiamata di funzione remota, che di fatto trasferisce l’esecuzione su una CPU remota.
Al momento del ritorno della funzione remota il controllo viene restituito alla CPU
chiamante. Se da un lato il singolo programma non trae alcun beneficio da un simile
approccio, dall’altro lato lanciare più programmi compilati in questo modo su una
macchina a memoria distribuita ha come risultato che i vari frammenti sono messi
in esecuzione su CPU differenti, di fatto utilizzando tutte le risorse di calcolo a disposizione. Questo pertanto può essere visto come un approccio “trasparente” alla
programmazione delle macchine a memoria distribuita.
1.1
Descrizione generale del sistema
Il sistema presentato si compone di un compilatore “distribuente” e di un ambiente
runtime “distribuito” adatto ad eseguire il bytecode generato dal compilatore stesso.
L’implementazione è da considerarsi un prototipo: si è scelto di concentrarsi maggiormente sulle tecniche di analisi piuttosto che sui dettagli relativi all’hardware ed
al compilatore stesso. L’ambiente runtime è come idea simile ad una Java Virtual
Machine, ma invece di eseguire il bytecode Java esegue il P-Code, ovvero il codice
1.1. Descrizione generale del sistema
3
intermedio del linguaggio Pascal. La macchina intermedia del Pascal è, come la
JVM, una macchina a stack, architettura che si contrappone alle macchine a registri, quali le CPU che sono installate in qualunque elaboratore. L’aver scelto Pascal
come linguaggio su cui sviluppare tutto il lavoro ha diversi risvolti interessanti per
il lavoro stesso: innanzitutto, il linguaggio scelto permette dichiarazioni di funzioni
annidate, e questo rende non banale il compito di decidere quali siano le sezioni di
codice che è possibile rendere indipendenti. Inoltre sviluppare un compilatore per
esso è molto semplice. Infine, la portabilità è garantita: infatti è sufficiente ricompilare la macchina virtuale per poter eseguire su qualunque architettura il codice
ottenuto dal compilatore.
1.1.1
L’ambiente runtime
Una macchina a stack è in tutto e per tutto una calcolatrice RPN. Chi è abituato
ad utilizzare una calcolatrice HP troverà il concetto della macchina a stack molto
familiare. Supponiamo di voler calcolare il valore dell’espressione seguente:
5 + 3 ∗ 8 − 4/6
Essa, equivale all’espressione in forma postfissa:
538 ∗ +46/−
Le istruzioni da eseguire per ottenere il risultato saranno pertanto:
push 5
push 3
push 8
mul
add
push 4
push 6
div
sub
L’espressione inoltre corrisponde al seguente albero, che è qualcosa di vagamente
simile all’albero di sintassi astratta prodotto dal compilatore:
1.1.2
Il compilatore
Il parser presente all’interno del compilatore, genera tramite una semplice tecnica
approfondita in seguito, denominata “a discesa ricorsiva”, l’albero di sintassi astratta. Una volta ottenuta una simile rappresentazione, una visita in post-ordine genera
4
1. Introduzione
sub
5
3
add
div
mul
4
6
8
Figura 1.1: Albero di sintassi astratta
il codice. L’algoritmo, molto informalmente, può essere rappresentato nel seguente
modo:
void g e n e r a t e c o d e (ASTNode ∗ node )
{
g e n e r a t e c o d e ( node−> l e f t ) ;
g e n e r a t e c o d e ( node−>r i g h t ) ;
node−>emit my co de ( ) ;
}
Prima di poter effettivamente emettere il codice è però necessario innanzitutto
capire se l’albero generato dal parser rappresenta un programma sensato, e questo
controllo è svolto dall’analisi semantica. In seguito si deve procedere alle analisi volte a capire quali dati condividono le funzioni. Esse si articolano in due macro-fasi:
la prima macro-fase ha il compito di capire effettivamente “chi usa cosa” all’interno
del codice. La seconda macro-fase ha il compito di allocare i dati in modo opportuno ai vari blocchi di codice eseguibile che si hanno in output. Tutto il lavoro di
implementazione si è svolto in due passi: prima sono stati scritti un compilatore
ed una macchina virtuale “standard”, ed in seguito li si sono modificati in modo
da supportare quanto proposto. Il lavoro più consistente è stato svolto dal lato del
1.2. Organizzazione del lavoro
5
compilatore. All’ambiente runtime è solo stata aggiunta un’istruzione ed è stata
modificata la semantica di altre due.
1.2
Organizzazione del lavoro
I successivi capitoli si sviluppano inizialmente presentando alcune tipologie di hardware parallelo e un paradigma per programmare una particolare classe di questo
hardware, ovvero le macchine a memoria distribuita. Il paradigma è il Message
Passing. In seguito vengono presentati in dettaglio il P-Code ed il compilatore, assieme ad alcune ulteriori osservazioni volte a parallelizzare il codice in maniera più
spinta, al fine di contestualizzare il capitolo 6, che parla delle tecniche di analisi
implementate.
6
1. Introduzione
2
Panoramica sulle architetture
parallele e distribuite
Negli ultimi anni abbiamo assistito ad un’incredibile esplosione delle performance
dei calcolatori. Per fare un esempio, nel 1984 un personal computer di fascia alta,
quale poteva essere L’HP-150 con l’unità disco 9153C aveva una CPU 8088 ad 8
MHz. Qualche anno più tardi, nel 1988, erano disponibili le CPU Intel 80286 a 12
MHz. A metà degli anni ’90 già erano disponibili processori ad oltre 100 MHz e
l’inizio di questo secolo ha visto i produttori di CPU infrangere la soglia di 1 GHz.
Dopo soli 5 anni dal 2000 è stata infranta la barriera dei 3 GHz.
La legge di Moore, che prende il nome da uno dei fondatori di Intel, sostiene
che il numero di transistori contenuti nei chip di memoria raddoppia ogni 18 mesi,
in altre parole la crescita predetta da Moore è esponenziale. Qualcuno ha adattato
questa legge anche alle prestazioni di calcolo dei chip. Se osserviamo bene l’evoluzione appena descritta, la legge di Moore sembra corretta. Tuttavia, nonostante in
ambito scientifico ed industriale la potenza di calcolo non sia mai sufficiente, prima
o poi questa crescita dovrà fermarsi a causa delle leggi fisiche. È infatti noto che i
segnali elettrici viaggiano sui cavi a velocità finita, pari a circa 23 c. Per esempio, a
clock elevati, una semplice curva delle linee di un bus parallelo porterebbe il segnale
che transita nelle linee più esterne ad arrivare a destinazione in ritardo rispetto a
quello che transita all’interno. Tale fenomeno è noto con il nome di bus skew. I
ritardi costringono pertanto a costruire circuiti sempre più piccoli, per permettere
al segnale di arrivare in tempo. Ma anche rimpicciolendo i transistori, oltre all’oggettiva difficoltà di farlo, si giunge al limite della dimensione dell’atomo. A tali scale
di grandezza diventano non trascurabili svariati fenomeni di natura quantistica.
Se la velocità della luce e le dimensioni infinitesime dei transistori sono dei limiti
insormontabili imposti dalla fisica, allora invece di cercare di abbatterli, è opportuno cercare di aggirarli, ed è a questo proposito che entra in gioco la computazione
8
2. Panoramica sulle architetture parallele e distribuite
parallela. Gli approcci al parallelismo (ed i problemi che insorgono) sono innumerevoli, ed una loro completa trattazione esula dagli scopi di questa tesi. [10] è un buon
punto di partenza per un approfondimento. Riguardo a questo tema, ci limiteremo a
identificare la categoria del parallelismo fine-grained e quella del parallelismo coarsegrained. Possiamo indicativamente dire che il parallelismo fine-grained è qualcosa
a livello di istruzione macchina, mentre il parallelismo coarse-grained è qualcosa a
livello di “architettura di calcolo”.
2.1
Parallelismo fine-grained
Il parallelismo di tipo fine viene implementato all’interno del singolo microprocessore,
tramite tecniche che permettono alle unità di calcolo di eseguire o più operazioni
contemporaneamente o la stessa operazione su più dati. Nel primo caso le operazioni
sono i passi fetch-decode-execute e parliamo di pipeline, nel secondo caso invece le
operazioni sono le istruzioni che una CPU può eseguire e parliamo di processore
vettoriale, ovvero di macchina SIMD in riferimento alla tassonomia di Flynn (Flynn,
1966). Esistono anche ulteriori tecniche ed ottimizzazioni: a livello di citazione si
possono indicare le CPU superscalari, che integrano più pipeline in modo da eseguire
più istruzioni contemporaneamente, l’esecuzione speculativa e la branch-prediction.
2.1.1
Pipeline
La pipeline si basa su un’osservazione molto semplice: le letture in memoria impiegano tempo, e durante le letture la CPU è ferma. Se facciamo in modo che la
CPU dopo aver letto un’istruzione la metta in esecuzione e contemporaneamente ne
prelevi un’altra, abbiamo (più o meno) ottenuto il risultato che la execution unit ha
sempre qualcosa da fare. In questo modello, detto pipeline a due stadi abbiamo l’esecuzione parallela della fase di fetch e della fase di decode+execute. Volendo, e nelle
CPU attuali viene fatto, si può aumentare il numero di stadi, in modo da aumentare
anche il grado di parallelismo. Questo però ha un prezzo, infatti nel caso in cui nel
programma ci sia un salto, parte del lavoro fatto dalla pipeline, in particolare quello
svolto fino alla decodifica dell’istruzione di salto, è sprecato. Gli attuali compilatori
ottimizzano il codice emesso al fine di evitare questo fenomeno, noto come “bolla”.
2.1.2
Processori vettoriali
Le CPU attuali si trovano normalmente alle prese con immagini e dati multimediali
in genere. Un’immagine ad esempio, può essere vista come un array di numeri
2.2. Parallelismo coarse-grained
9
che rappresentano il valore di ogni singolo pixel. Alternativamente, se abbiamo
un’immagine I di N ∗ M pixel, essa sarà rappresentata da un vettore contenente
N ∗ M quadruple nella forma P = hA, R, G, Bi. Normalmente R, G, B e A sono
valori ad 8 bit (1 byte), per cui se volessimo rappresentare I avremmo bisogno di
N ∗ M ∗ 4 byte. Una spiegazione pratica e molto semplicistica del funzionamento
di un’unità vettoriale è la seguente: un banale filtro potrebbe voler aggiungere una
quantità fissata, diciamo k, ad ogni pixel (l’effetto è quello di sbiadire l’immagine).
L’approccio standard è il seguente:
unsigned char ∗ img = new unsigned char [N∗M∗ 4 ] ;
l o a d i m a g e ( img ) ;
for ( i nt i = 0 ; i < N∗M∗ 4 ; i ++)
i f ( i % 4 != 0 )
/∗ s a l t a l ’ a l p h a c h a n n e l ∗/
img [ i ] += k ;
Immaginiamo ora un pixel come un vettore. L’algoritmo diventa il seguente:
vector unsigned char ∗ img = new vector unsigned char [N∗M] ;
vector unsigned char qty = { 0 , k , k , k } ;
l o a d i m a g e ( img ) ;
for ( i nt i = 0 ; i < N∗M; i ++)
vec a dd ( img [ i ] , img [ i ] , qty ) ;
Trascurando il dettaglio che in una situazione simile il pixel può essere visto come un
intero a 32 bit, quello che abbiamo fatto è stato di sommare invece che due scalari,
due vettori di 4 elementi, potenzialmente utilizzando lo stesso tempo che avremmo
impiegato per la somma scalare, ottenendo uno speedup ideale di 4. Ogni moderna
CPU integra un’unità vettoriale: AltiVec, VIS ed SSE sono le implementazioni delle
CPU PowerPC, SPARC e x86. I “veri” computer vettoriali, un esempio su tutti i
sistemi CRAY, sono qualcosa di più sofisticato ma l’idea su cui si basano è la stessa.
2.2
Parallelismo coarse-grained
Quando prendiamo molte CPU, le colleghiamo in qualche modo e le facciamo lavorare insieme, parliamo di parallelismo a grana grossa. Se le CPU sono collegate allo
stesso bus per accedere alla memoria, parliamo di architetture a memoria condivisa.
Altrimenti, se prendiamo qualche personal computer, li colleghiamo via ethernet e
ci installiamo MPI, abbiamo costruito un sistema a memoria distribuita.
10
2. Panoramica sulle architetture parallele e distribuite
Figura 2.1: Multiprocessore a memoria condivisa
2.2.1
Architetture a memoria condivisa
I multiprocessori a memoria condivisa sono il modo più semplice di implementare una macchina parallela, ed anche quelli più facili da programmare. Infatti, un
software scritto per macchine monoprocessore gira senza modifiche su macchine multiprocessore, e se strutturato in thread trae beneficio in modo trasparente dalle CPU
aggiuntive. Ovviamente, la semplicità del modello shared-memory porta con se degli inconvenienti notevoli. È facile rendersi conto che, essendo le CPU connesse allo
stesso bus, esse competono per l’accesso, ed in linea teorica, se B è la banda disponibile sul bus ed n è il numero di CPU, ogni singola CPU potrà contare su una
banda di Bcpu =
B
n.
Già quando si arriva ad 8 CPU si vede che il modello a memoria
condivisa standard funziona male, e per questo è necessario introdurre architetture di tipo NUMA. Lo sviluppo delle CPU inoltre ha visto un’evoluzione molto più
rapida di quella delle memorie e questo ha portato ad introdurre una gerarchia di
queste ultime, in primis le cache. Nel momento in cui diverse CPU si trovano a
lavorare sullo stesso insieme di dati, sorgono problemi di coerenza della cache che
non possono essere trascurati.
2.2.2
Architetture a memoria distribuita
Quando sono necessarie moltissime CPU, non potendo adottare il modello a memoria
condivisa, si dota ogni nodo di memoria propria, e lo si connette agli altri tramite reti ad alta velocità e bassa latenza, quali InfiniBand o Myrinet. L’approccio
alla programmazione però è completamente diverso, infatti questi sistemi vengono
programmati con il paradigma del message-passing, che porta con se una maggiore
difficoltà in termini di programmazione. In ambienti a memoria distribuita il non
scrivere il proprio codice ad hoc porta alla completa impossibilità di trarre un benefi-
2.3. Programmazione delle macchine a memoria distribuita con MPI
11
Figura 2.2: Macchina a memoria distribuita
cio da queste architetture, a differenza del caso delle macchine a memoria condivisa,
dove, lanciando diversi processi CPU-bound, è il sistema operativo ad occuparsi del
bilanciamento del carico. MOSIX, software nato all’università di Gerusalemme, ha
tentato di raccogliere i benefici di entrambe le architetture in una tipologia di clustering denominata Single System Image, ma, pur essendo un progetto estremamente
valido, non ha riscosso il giusto successo. Qualcosa di simile è correntemente in fase
di implementazione all’interno della variante DragonFly del sistema BSD. A differenza di MOSIX, che è una piccola patch del kernel Linux, DragonFlyBSD è una
fork del sistema FreeBSD, progettata con l’obiettivo di ottenere proprio un sistema
operativo distribuito che supporti nativamente il clustering SSI.
2.3
Programmazione delle macchine a memoria distribuita con MPI
Visto l’obiettivo della tesi, si è reso necessario far comunicare tutte le macchine
virtuali su cui gira il codice in modo distribuito. Molto probabilmente si sarebbe
rivelato opportuno progettare uno strato con delle primitive di comunicazione tra
macchine virtuali pensate ad-hoc per questa applicazione, ma per motivi di semplicità si è scelto di utilizzare MPI. MPI non è altro che una libreria di message-passing
pensata per il calcolo ad alte prestazioni. MPI è inoltre lo standard de-facto per
quanto riguarda le librerie di comunicazione nei sistemi a memoria distribuita. Esistono decine di diverse implementazioni di questa libreria di message passing. Le più
comuni sono senz’altro MPICH, MVAPICH (MPI over Verb API, implementazione
specifica per l’utilizzo su reti InfiniBand), LAM-MPI. Molte delle implementazioni
disponibili stanno però convergendo su OpenMPI, progetto che mira a creare la migliore libreria di message-passing disponibile, raccogliendo gli sforzi di tutti i progetti
12
2. Panoramica sulle architetture parallele e distribuite
che ruotano attorno ad essa. È stata utilizzata proprio OpenMPI per implementare
parte del software oggetto di questa tesi. Altra libreria degna di nota, ma non della
famiglia di MPI è PVM (Parallel Virtual Machine). Verranno ora presentati i concetti e le primitive strettamente necessari allo sviluppo di questa tesi. La libreria è
qualcosa di molto più esteso e versatile, ed esite un’ampia documentazione di essa.
Per ulteriori approfondimenti si veda, ad esempio [9].
2.3.1
Concetti alla base di MPI
MPI, come detto, è una libreria di message passing, disponibile per C, C++ e Fortran, adatta ad essere utilizzata su numerose tipologie di architetture a memoria
distribuita. Il compito principale di MPI è quello di astrarre dalla specifica tipologia
di interconnessione dei vari nodi di un sistema, sia essa Ethernet, InfiniBand, Myrinet o quant’altro, offrendo un modo semplice e snello di eseguire le comunicazioni
tra i processi.
Parlando di Message Passing, ci aspettiamo quantomeno un modo per inviare e ricevere dei messaggi. MPI mette a disposizione le funzioni MPI_Send e MPI_Recv a
questo scopo [9]. Di seguito i loro prototipi:
MPI_Send (void *msgbuf
/* in */,
int count
/* in */,
MPI_Datatype dt
/* in */,
int destination
/* in */,
int tag
/* in */,
MPI_Comm comm
/* in */);
MPI_Recv (void *msgbuf
/* out */,
int count
/* in */,
MPI_Datatype dt
/* in */,
int source
/* in */,
int tag
/* in */,
MPI_Comm comm
/* in */
MPI_Status* status
/* out */);
All’avvio di un programma parallelo basato su MPI, viene stabilito il numero di
processi: in altre parole, i processi che fanno parte del programma sono gli stessi
dall’inizio alla fine. Ogni processo possiede un identificatore, il rank, valore di tipo
2.3. Programmazione delle macchine a memoria distribuita con MPI
13
intero. Nel caso un programma sia composto da p processi, il rank sarà compreso nell’intervallo 0, 1, 2, ..., p − 1. Il rank è unico, ovvero non esistono due processi
con lo stesso rank. Osservando i prototipi di MPI_Send e MPI_Recv, notiamo rispettivamente due parametri, destination e source. Nel caso della trasmissione
del messaggio, destination rappresenta il rank del processo a cui vogliamo spedire
qualcosa. Analogamente, nel caso della ricezione, source rappresenta il rank del
processo da cui vogliamo ricevere qualcosa.
Un esempio banale dell’utilizzo delle due funzioni appena descritte potrebbe essere
il seguente:
/∗ P r o c e s s o che i n v i a un m e s s a g g i o ( rank 0) ∗/
#define BUFSZ 10
char buf [ BUFSZ ] ;
s t r n c p y ( buf , pippo , BUFSZ)
MPI Send(&buf , s t r l e n ( buf ) , MPI CHAR,
1 , 0 , MPI COMM WORLD ) ;
/∗ P r o c e s s o che r i c e v e un m e s s a g g i o ( rank 1) ∗/
MPI Recv(&buf , BUFSZ, MPI CHAR,
0 , 0 , MPI COMM WORLD, &s t a t u s ) ;
Generalmente entrambe le precedenti istruzioni trovano posto nello stesso programma, l’esecuzione di una piuttosto che dell’altra è decisa a runtime in base al rank
del processo.
L’esempio seguente, tratto da [9], mette chiaramente in luce gli aspetti di base della
programmazione con MPI.
2.3.2
Esempio di utilizzo: Integrazione numerica con MPI
Un semplicissimo modo di calcolare l’integrale definito di una funzione, ad esempio
f (x), è quello di suddividere il suo dominio in un certo numero, diciamo n, di intervalli. Una volta fatto ciò, proiettando ogni suddivisione sul grafico della funzione e
congiungendo con dei segmenti i punti cosı̀ ottenuti, otteniamo una serie di trapezi.
Sommando la loro area si ottiene un’approssimazione dell’integrale cercato. Supponiamo che tutte le suddivisioni siano di uguale lunghezza: dati a e b gli estremi di
integrazione, pertanto, la lunghezza della base di ogni trapezio sarà:
B=
b−a
n
14
2. Panoramica sulle architetture parallele e distribuite
Le basi dei singoli trapezi saranno pertanto gli intervalli [a, a + B], [a + B, a + 2B], ....
Più in generale, la base dell’i-esimo trapezio sarà l’intervallo:
[a + (i − 1)B, a + iB].
Sia ora xi = a + iB, con 0 < i < n. I lati sinistro e destro di ogni trapezio saranno
pertanto dati rispettivamente da f (xi−1 ) e f (xi ). Da questo ragionamento si deduce
che l’area dell’i-esimo trapezio sarà data da:
B[f (xi−1 ) + f (xi )]
2
L’area totale tra gli estremi di integrazione scelti pertanto sarà data dalla sommatoria:
n
X
B[f (xi−1 ) + f (xi )]
i=0
2
che con semplici passaggi si trasforma in:
n−1
f (x0 ) + f (xn ) X
B
f (xi )
+
2
i=1
Implementare un simile procedimento in modo sequenziale si riduce a poco più di
un ciclo for.
double i n t e g r a t e ( double ( ∗ f ) ( double x ) ,
double a , double b , i nt n )
{
double r e s u l t , B, x ;
i nt i ;
B = ( b−a ) / n ;
r e s ul t = ( f (a) + f (b ))/2;
x = a;
for ( i nt i = 1 ; i < n ; i ++)
{
x += B;
r e s u l t += f ( x ) ;
}
r e s u l t ∗= B ;
return r e s u l t ;
}
Volendo parallelizzare questo algoritmo, l’idea è quella di far calcolare i valori di
f (x) in diversi sottointervalli di [a, b] a diversi processi. Se ad esempio abbiamo a
disposizione 4 processori, e vogliamo calcolare l’integrale utilizzando n = 100, allora
2.3. Programmazione delle macchine a memoria distribuita con MPI
15
assegneremo 25 punti per processore. Essendo quello di MPI un approccio SPMD,
decideremo in quale intervallo eseguire i calcoli in base al rank assegnato al singolo
processo. Di seguito lo pseudo-codice.
void p a r a l l e l i n t e g r a t e ( double ( ∗ f ) ( double x ) ,
double a , double b , i nt n )
{
B = ( b−a ) / n ;
l o c a l n = n/ t o t a l p r o c e s s e s ;
l o c a l a = a+my rank ∗ l o c a l n ∗B ;
l o c a l b = l o c a l a + l o c a l n ∗B ;
r e s u l t = integ r a te ( f , local a , local b , local n , B) ;
i f ( rank == 0 )
{
double r c v ;
for ( i nt s r c = 1 ; i < n ; i ++)
{
MPI Recv(&rcv , 1 , MPI DOUBLE, s r c , [ . . . ] ) ;
r e s u l t += r c v ;
}
}
else
{
MPI Send(& r e s u l t , 1 , MPI DOUBLE, 0 , [ . . . ] )
}
i f ( rank == 0 )
printf ( result );
}
2.3.3
Compilazione ed utilizzo del software in ambiente MPI
Una volta scritto il proprio codice, al fine di poterlo rendere eseguibile, le implementazioni di MPI disponibili mettono solitamente a disposizione dei wrapper per
il compilatore di sistema. Tale wrapper, (mpicc, mpif77, ..) si occupa di collegare
l’eseguibile con tutte le opportune librerie. In seguito, è necessario lanciare il proprio
codice tramite il runtime MPI, e per questo viene fornito il comando mpirun. Nel
caso di OpenMPI, mpirun si aspetta di avere in input un hostfile, nel quale sono
specificate tutte le macchine disponibili nel proprio cluster. Una volta ottenuti gli
indirizzi IP di tutti gli host, mpirun lancia su ogni macchine orted, ed in seguito
l’eseguibile MPI.
Il demone orted, parte integrante di OpenMPI, si occupa di gestire tutte le comunicazioni relative al message-passing tra i vari nodi del cluster. Pertanto, una
volta compilato il proprio codice, volendolo far eseguire su n CPU, si darà un co-
16
2. Panoramica sulle architetture parallele e distribuite
mando del tipo: mpirun -np n -hostfile myhostfile.dat ./myprogram.
3
P-Code e P-Machine
Il P-Code è il linguaggio macchina della P-Machine, una macchina intermedia di
alcune implementazioni di Pascal. Questa macchina viene implementata via software su delle architetture fisiche. Il perché si dovrebbe voler far eseguire del codice
macchina ad un software è dettato da motivi che sono i più svariati:
• Portabilità degli eseguibili risultanti dal codice sorgente su sistemi operativi e
hardware diversi.
• Facilitazioni nel debugging
• Facilitazioni nella scrittura del compilatore
• Più generalmente, riduzione della complessità di implementazione del linguaggio
Le motivazioni appena elencate hanno portato diversi implementatori a strutturare
i loro linguaggi di programmazione in modo da essere compilati in codice astratto
e poi essere eseguiti da una macchina astratta [3]. Altri linguaggi oltre Pascal che
appartengono a questa categoria sono Java (compilato in Java Bytecode), Basic
(anche esso in P-Code), BCPL (in O-code).
Il P-Code mette a disposizione una serie di insiemi di istruzioni che ricordano
molto quelle di una macchina hardware, tranne per il fatto che solo dove è strettamente necessario prendono uno o più operandi. Questo è dovuto alla natura a stack
della macchina, che conferisce al suo codice delle caratteristiche leggermente di più
alto livello rispetto ad un assembly di una macchina a registri. La macchina in realtà
possiede alcuni registri, ma che servono soltanto al funzionamento della macchina
stessa e non sono accessibili al programmatore.
18
3. P-Code e P-Machine
Figura 3.1: Struttura a livelli del linguaggio Pascal
3.1
I registri della P-Machine
Prima di poter analizzare in dettaglio quali siano le istruzioni della P-Machine, è
necessario comprendere il significato dei suoi registri.
3.1.1
PC - Il program counter
Per programma si intende nient’altro che una lista di istruzioni in linguaggio macchina che si susseguono. Il program counter è pertanto responsabile di indicare in ogni
momento l’istruzione in esecuzione all’interno del programma. Esso, come vedremo
in seguito, viene modificato dalle istruzioni di salto e dalle istruzioni di chiamata e
ritorno da procedura.
3.1.2
SP - Stack Pointer
In ogni istante, il programma necessita dei dati su cui lavorare. Un programma
che non elabora alcun dato, infatti, ha tutta l’aria di essere poco utile, se non per
sprecare cicli di CPU. Come si è visto in precedenza, e come sarà approfondito in
seguito, l’esecuzione del programma si basa su uno stack, e il registro SP punta
costantemente alla sua cima.
3.2. Istruzioni aritmetico/logiche
3.1.3
19
MP - Mark Stack Pointer
Il registro MP tiene traccia dell’inizio del frame della procedura correntemente in
esecuzione. Il suo funzionamento sarà chiaro in seguito, analizzando le istruzioni di
caricamento dalla memoria e di chiamata.
3.2
Istruzioni aritmetico/logiche
Le istruzioni aritmetiche messe a disposizione dal P-Code sono le classiche presenti
in qualunque architettura di calcolo. Pertanto, verrà esposto il funzionamento di
una sola di esse, essendo identico a quello di tutte le altre.
Ogni operazione aritmetica prende i propri parametri dallo stack, pertanto all’occorrenza di una di esse ci troviamo di fronte ad un listato simile al seguente:
...
ADD
...
Eseguendo la ADD, la macchina astratta si occupa di estrarre gli ultimi due elementi
presenti sulla cima dello stack, addizionarli, e porre il risultato di nuovo in cima allo
stack. Ogni operazione aritmetica presenta due diverse versioni, una per gli interi
ed una per i reali. Nel caso di ADD i due opcode sono rispettivamente ADI e ADR.
Ovviamente le operazioni che non hanno senso sui numeri reali, quali il modulo,
hanno solo la versione intera, ad esempio MOD. L’esecuzione da parte dell’ambiente
runtime rispecchia molto da vicino il seguente pseudo-codice:
20
3. P-Code e P-Machine
while ( t r u e )
{
instruction inst = fetch ( ) ;
switch ( i n s t )
{
[...]
case ADI :
SP −= 4 ;
op2 = m memory−>r e a d i n t (SP ) ;
SP −= 4 ;
op1= m memory−>r e a d i n t (SP ) ;
m memory−>w r i t e i n t (SP , op1+op2 ) ;
SP += 4 ;
break ;
[...]
}
}
Di fatto, per ogni istruzione da eseguire, viene svolta una sequenza di operazioni
fetch-decode-execute simili a quelle eseguite da una qualunque CPU. Pertanto, per
osservare nel dettaglio come vengono eseguite le altre istruzioni, si rimanda al codice
sorgente, e precisamente al modulo ExecutionUnit.cpp
3.3
Istruzioni di LOAD/STORE
Questa categoria di istruzioni è necessaria al fine di poter caricare i dati nell’area di
lavoro del programma. Essendo la macchina del P-Code una macchina a stack e non
a registri, potrebbe sembrare strano avere delle istuzioni che eseguono, ad esempio,
dei caricamenti “da memoria a memoria”. Tuttavia, se ricordiamo il funzionamento
di una qualsiasi istruzione aritmetica, notiamo che ciò è necessario. Osserviamo il
seguente frammento di programma:
var k : integer ;
k := 5 ;
[...]
procedure sum k ( a , b : integer )
begin
sum k := a + b + k ;
end sum k ;
Tralasciando l’utilità di un simile programma, una volta tradotto in P-Code, il
risultato è il seguente:
LDA
1, 4
; indirizzo di k
3.3. Istruzioni di LOAD/STORE
LDC
5
; valore da caricare
LDA
0, 0
; indirizzo dove salvare il valore di ritorno
LDA
0, 4
; indirizzo di a
0, 5
; indirizzo di b
21
STO
[...]
LOD
LDA
LOD
ADD
; eseguo la somma
LDA
1, 4
; indirizzo di k
LOD
; valore di k
ADD
; eseguo la somma
STO
; salvo il tutto nella locazione del valore di ritorno
Si può notare che, ad esempio nel caso del caricamento del valore di a, si procede
nel seguente modo:
• LDA 0, 4: Load Address, scope corrente, variabile all’offset 4. Viene caricato
l’indirizzo della variabile a.
• LOD: Load Indirect, viene dereferenziato l’indirizzo presente in cima allo stack,
in modo da sostituirlo con il valore presente a tale indirizzo.
• Si ripete il procedimento analogo per b
• Ora sullo stack sono presenti i valori di a e b, si può procedere alla somma.
Cosı̀ facendo, ogni istruzione trova i suoi operandi subito in cima allo stack. Ma
vediamo in dettaglio il funzionamento delle istruzioni disponibili.
3.3.1
LDA - Load Address
Pascal, a differenza di altri linguaggi, ad esempio C, ammette uno scoping “non
piatto”. In altre parole, sono ammesse dichiarazioni di funzioni innestate. Un
programma simile è perfettamente legale:
22
3. P-Code e P-Machine
program n e s t e d f u n c t i o n s ;
var a : integer ;
procedure f ( ) ;
var b : integer ;
procedure g ( ) ;
var c : integer ;
begin
(∗ corpo d i g ∗ )
end g ;
begin
(∗ corpo d i f ∗ )
end f ;
(∗ corpo d e l programma p r i n c i p a l e ∗ )
end n e s t e d f u n c t i o n s .
Tuttavia, questo richiede un certo supporto a runtime, ovvero il mantenimento della
catena statica. La catena statica altro non è che una rappresentazione del modo
in cui i blocchi sono innestati “a livello di testo”. L’utilità della catena statica si
manifesta nel momento in cui è necessario accedere a variabili non locali. Vediamo
prima però come avviene l’accesso alle variabili locali. Innanzitutto, è necessario
rendersi conto che fino a quando una funzione non viene eseguita, lo spazio per i
suoi dati non viene allocato. Nel momento in cui la procedura viene chiamata, il
chiamante si occupa di creare il frame che contiene:
• Valore di ritorno
• Legame statico
• Legame dinamico
• Indirizzo di ritorno
• Parametri attuali
I primi quattro dati sono tutti indirizzi, ed essendo la nostra una macchina a 32 bit,
occupano esattamente 4 word. I parametri infine, occuperanno lo spazio relativo
al loro tipo di dato. Ad esempio, nel caso di due parametri di tipo integer, si
avrà un’occupazione di due ulteriori word. L’inizio dello spazio utile per le variabili
locali, ricordando il significato del registro MP, si troverà per cui all’indirizzo MP + 6.
Supponiamo ora, in riferimento al programma precedente, che dal corpo di g si voglia
accedere alla variabile c. Non avendo parametri, rispetto all’esempio precedente,
vengono risparmiate 2 word, per cui c si troverà all’indirizzo MP + 4. Quando ci
si trova nella necessità di dover caricare c, pertanto dovremmo in qualche modo
3.3. Istruzioni di LOAD/STORE
23
eseguire qualcosa di simile ad un LDA (MP+4), al fine di ottenere l’indirizzo assoluto
di c. Nel caso in cui invece g voglia accedere a b, il meccanismo dovrebbe essere
lo stesso, ad eccezione che l’offset andrebbe riferito al frame di f . Ricordiamo che
affinché g possa essere chiamata deve essere stata chiamata anche f , precisamente,
il programma principale chiama f ed f chiama g. In altre parole, i frames delle
funzioni “testualmtente” più esterne, devono essere presenti sullo stack. Il legame
statico serve proprio a poter risalire al frame, in questo caso, di f . Essendo che f è
al livello subito sopra di quello di g, la catena statica va risalita di 1. Per caricare
b pertanto sarà sufficiente eseguire LDA nel seguente modo: LDA 1, 4 (4 è l’offset
rispetto al frame di f ).
3.3.2
LDI - Load Immediate
L’istruzione Load Immediate è banale, e durante la sua esecuzione la macchina
astratta non fa altro che prendere il suo operando e porlo in cima allo stack. Un
valore immediato è una costante priva di nome inserita direttamente nel codice, ad
esempio nell’espressione x := 5;.
3.3.3
LDC - Load Constant
Il caricamento di una costante è un’istruzione estremamente semplice. Infatti, si
limita a prendere l’indirizzo della costante specificata dalla tabella delle costanti e a
caricarla sullo stack, in modo molto analogo ad LDA.
3.3.4
LOD - Load Indirect
Anche l’istruzione di dereferenziazione ha un funzionamento molto semplice. All’esecuzione, la macchina astratta non fa altro che sostituire l’indirizzo di memoria in
cima allo stack (l’argomento di LOD) con ciò che è effettivamente contenuto a quel
dato indirizzo.
3.3.5
STO - Store
La Store è l’esatto opposto della LOD. Sullo stack si aspetta sulla cima un valore
e subito dopo un indirizzo. All’esecuzione della Store, tale valore verrà posto in
memoria all’indirizzo presente come secondo elemento dello stack.
24
3. P-Code e P-Machine
Figura 3.2: Collocazione di un array in memoria
3.4
Istruzioni di accesso con indice
Il P-Code mette a disposizione un’istruzione per l’accesso indicizzato agli array, tale
istruzione è la IXA (Compute Indexed Address). Il suo funzionamento è molto
semplice e potente. Il seguente frammento di codice esegue l’accesso ad un array:
program a r r a y a c c e s s ;
var a : array 5 of integer ;
begin
a [ 3 ] = 12345;
end a r r a y a c c e s s ;
Un array a è un’area contigua di memoria che contiene un certo numero di dati, del
tipo specificato, T . Alla luce di ciò è molto semplice intuire che per eseguire l’accesso
ad un array è sufficiente conoscere il suo indirizzo di memoria, l’indice dell’elemento
voluto, e la dimensione del singolo elemento. Definiamo pertanto:
• base(a), che ci restituisce l’indirizzo a cui inizia l’array
• sizeof (T ), che ci restituisce la dimensione del tipo di dati di cui è formato
l’array
L’n-esimo elemento si troverà pertanto all’indirizzo:
base(a) + n ∗ sizeof (T )
L’istruzione IXA si aspetta pertanto:
• di trovare base(a) sullo stack
• di avere n e sizeof (T ) come operandi
3.5. Istruzioni di salto e di confronto
25
Una volta che IXA è stata eseguita sotto queste condizioni, essa lascia sullo stack
l’indirizzo dell’elemento desiderato, e con una semplice LOD possiamo dereferenziare tale indirizzo ed ottenere sullo stack l’elemento dell’array indicato ad IXA. In
riferimento al frammento di programma precedente, la sua traduzione in P-Code è:
LDA
0, 4
; Carica l’indirizzo di a
IXA
3, 1
; n = 3, sizeof(T) = 1, indirizzo di a[3]
LDI
12345
; Carica il valore 12345
STO
3.5
; Memorizzalo in a[3]
Istruzioni di salto e di confronto
Ogni programma deve essere in grado di eseguire dei salti: in caso contrario non
potremmo eseguire blocchi di codice in modo condizionato oppure in ciclo. Il P-Code
definisce due sole istruzioni di salto, il salto incondizionato e il salto su condizione
falsa.
3.5.1
UJP - Unconditional Jump
L’istruzione UJP prende come operando un indirizzo di memoria. L’esecuzione
consiste solamente nel caricare il Program Counter con il valore dell’operando.
3.5.2
FJP - Jump On False
L’esecuzione dell’istruzione FJP è leggermente più complessa. Infatti, presuppone
che subito prima venga eseguita un’istruzione di confronto. Vediamo un frammento
di codice Pascal e relativa traduzione in P-Code.
x := 1 ;
y := 2 ;
i f x < y then
[...]
else
[...]
end ;
26
3. P-Code e P-Machine
start:
LDA
<indirizzo di x>
LDC
1
STO
LDA
<indirizzo di 2>
LDC
2
STO
LDA
<indirizzo di x>
LOD
LDA
<indirizzo di y>
LOD
LSS
FJP
<indirizzo else>
<codice ramo then>
UJP
exit_if
; x := 1
; y := 2
;
;
;
;
;
carica l’indirizzo di x
carica il suo valore
carica l’indirizzo di y
carica il suo valore
è minore?
else:
<codice ramo else>
exit_if:
LSS è un’istruzione di confronto, ed il suo funzionamento è simile a quello di
una qualsiasi istruzione aritmetica. La differenza sta nel fatto che le istruzioni di
confronto lasciano sullo stack un valore booleano invece che, ad esempio, un intero.
Nel caso di LSS, viene lasciato sullo stack il valore “true” nel caso il primo operando
sia minore del secondo. Il funzionamento di FJP a questo punto è chiaro: nel caso
sullo stack, dopo aver eseguito LSS, sia presente il valore “false”, si ha l’esecuzione
del salto.
3.6
Istruzioni relative alle chiamate
L’ultima categoria di istruzioni che prendiamo in esame è la classe delle istruzioni
di chiamata e di ingresso nelle procedure.
3.6.1
Istruzioni relative al chiamante
Il chiamante, per poter chiamare una procedura deve:
• Allocare spazio per: l’indirizzo di ritorno, il legame statico, il legame dinamico
e il valore di ritorno (stack frame, istruzione MST)
• Allocare i parametri
• Eseguire la chiamata (istruzione CUP)
3.6. Istruzioni relative alle chiamate
27
[...]
procedure f a t t ( n : integer ) : integer ;
begin
i f n < 2 then
f a t t := 1 ;
else
f a t t := n∗ f a t t ( n − 1 );
end ;
end f a t t ;
[...]
k :=5;
n := f a t t ( k ) ;
[...]
Una tipica sequenza di chiamata per fatt è la seguente:
LDA
<indirizzo di k>
LDC
5
; k := 5
STO
MST
0
; preparo lo stack frame
LDA
<indirizzo di k>
; carico il parametro attuale k
<indirizzo di fatt>
; chiamo fatt
LOD
CUP
MST - Mark Stack
L’operando dell’istruzione MST serve a specificare il dislivello di annidamento tra
gli ambienti di chiamante e chiamato, e serve per il legame statico. Specificare 1
equivale a dire che si sta chiamando una funzione allo stesso livello di scoping, 2 si
sta chiamando al livello padre e cosı̀ via. Si specifica 0 nel caso si voglia chiamare
una procedura locale.
CUP - Call User Procedure
Osservando il precedente esempio di codice, l’esecuzione di CUP è di semplice comprensione. Infatti, dopo aver creato il frame per la funzione da eseguire tramite
MST, e dopo aver caricato i parametri sullo stack, quello che rimane da fare è salvare nello spazio creato da MST l’indirizzo dell’istruzione da eseguire subito dopo il
ritorno dal chiamato, e ricaricare il registro PC con l’indirizzo del punto di ingresso
della funzione da chiamare. Quello appena descritto è proprio il compito di CUP.
28
3. P-Code e P-Machine
Figura 3.3: Stack frame
3.6.2
Istruzioni relative al chiamato
Il chiamato non deve fare nient’altro che allocare spazio per le proprie variabili, utilizzando l’istruzione ENT. ENT si limita ad incrementare il valore dello stack pointer
di quanto specificato tramite l’operando. Terminata l’esecuzione, servendosi di RET
il chiamato provvede alla distruzione dello stack frame e a ritornare il controllo al
chiamante. RET è il duale di CUP, infatti, tramite RET il Program Counter viene
caricato con l’indirizzo di ritorno memorizzato nella zona creata dall’istuzione MST.
4
Architettura del compilatore
Pianificando lo sviluppo del software presentato si è posto il problema di decidere
se utilizzare un compilatore già pronto e modificarlo o se scrivere un compilatore ed
una virtual machine da zero. Principalmente per due motivi si è scelto di scrivere
l’intero sistema da zero. Innanzitutto i compilatori disponibili o erano troppo complessi, per cui il tempo necessario a capirli sarebbe stato pari se non superiore alla
scrittura di uno nuovo, oppure erano troppo “cablati” per semplicità implementativa e la loro modifica si sarebbe rivelata quasi una riscrittura. Inoltre, i compilatori
valutati “complessi” erano fatti per compilare in codice nativo. Questo avrebbe
creato svariati problemi implementativi. Il compilatore che è stato scritto si basa
volutamente su un’architettura estremamente semplice e priva di alcune componenti
presenti in qualunque compilatore professionale. Ciò ha permesso un rapido sviluppo. Inoltre, tale struttura permette una veloce comprensione da parte di chi voglia
studiarne il funzionamento interno. Nonostante il linguaggio Pascal ben si presti
ad essere compilato in una singola passata, questo compilatore ne effettua diverse,
ognuna con un ben preciso scopo.
• Analisi lessicale
• Analisi sintattica
• Analisi semantica
• Generazione del codice eseguibile
Brevemente, la fase di analisi lessicale è responsabile di tradurre il testo del programma in entità di più alto livello, ovvero i token. Di seguito, l’analisi sintattica
ha il compito di verificare che le stringhe di token che si ricevono in ingresso siano
grammaticalmente corrette. Un token rappresenta un’unità atomica del linguaggio
che si vuole compilare, ad esempio una parola riservata (begin,end,if,while) oppure
30
4. Architettura del compilatore
un operatore matematico, un identificatore e cosı̀ via. La traduzione da testo a token
è svolta più precisamente dallo scanner o lexer. I token da esso generati rappresentano l’input del parser. È quest’ultimo che si occupa di verificare la correttezza
grammaticale del flusso di token in ingresso. Pur essendo entità distinte, scanner e
parser lavorano in stretta accoppiata, in quanto il primo è continuamente chiamato dal secondo per ottenere nuovi oggetti sintattici. Questa fase genera l’albero di
sintassi astratta (Abstract Syntax Tree).
Successivamente si ha la fase di analisi semantica. Essa ha il delicato compito
di comprendere se il programma che il compilatore riceve in ingresso ha un senso.
Ad esempio, è nella fase di analisi semantica che il compilatore genera un errore
se si è tentato ad esempio di assegnare un intero ad un record. Infine, vi è la fase
di generazione del codice, che si occupa di tradurre l’albero di sintassi astratta in
P-Code.
L’albero di sintassi astratta è una struttura dati fondamentale per un compilatore,
ma non è l’unica. Senza una tabella dei simboli, il compilatore non riuscirebbe a
fare molto. In essa infatti, sono memorizzate tutte le informazioni relative ai tipi,
alle variabili, alle funzioni ed alle costanti. Ad esempio è la tabella dei simboli che
custodisce l’informazione che una variabile è di tipo intero oppure che una funzione
prende n parametri.
4.1
Introduzione al concetto di linguaggio formale
Prima di passare ad una descrizione più approfondita dell’effettivo funzionamento
di qualunque compilatore è necessario comprendere delle caratteristiche strutturali proprie di ogni linguaggio. Vi sono svariate tipologie di linguaggi, ognuna con
diverso potere espressivo. Al fine di questa semplice trattazione ci basta prendere
in considerazione i linguaggi regolari ed i linguaggi liberi dal contesto. Per ulteriori
approfondimenti si veda ad esempio [2].
Per poter parlare di linguaggi formali si rende necessaria l’introduzione di alcune
definizioni. La prima di esse è quella di simbolo, il quale è un’entità primitiva di un
linguaggio, che non è precisamente definita ed il cui significato è dato per scontato,
come, ad esempio, nel caso di un punto in geometria.
4.1.1
Linguaggi regolari
I simboli da soli non servono a molto, pertanto, per arrivare a parlare di linguaggio
formale è necessario introdurre alcuni altri concetti. L’alfabeto Σ di un linguaggio è
4.1. Introduzione al concetto di linguaggio formale
31
l’insieme dei simboli validi nell’ambito del linguaggio stesso, esattamente come nel
caso dell’italiano che è costruito sull’alfabeto latino. Una stringa è una concatenazione di simboli presi dall’alfabeto. Di nuovo, l’analogia con la lingua parlata è con
la parola. Il linguaggio L per cui è un insieme di stringhe di simboli appartenenti
all’alfabeto Σ. Un linguaggio regolare è un linguaggio riconosciuto da un automa a
stati finiti. Questo “dispositivo” è fatto in modo da leggere un simbolo e cambiare
stato di conseguenza. Ad esempio, l’insieme di tutti i numeri divisibili per quattro
e rappresentati in base due, è un linguaggio regolare. Intuitivamente, ogni numero
binario divisibile per quattro deve avere le due cifre meno significative uguali a zero.
Dobbiamo far pertanto in modo che, dopo aver letto due zeri, l’automa si trovi in
uno stato detto “di accettazione”, ovvero che ci indica che è stato letto un numero
con le caratteristiche richieste. Il seguente automa riconosce questo linguaggio, e lo
stato di accettazione è q2 :
q0
q1
q2
0
q1
q2
q2
1
q0
q0
q0
Supponiamo ora di voler riconoscere tutte e sole le stringhe di lungezza 5 che siano
palindrome, quali ad esempio la parola “radar”. Nel momento in cui l’automa si trova
a dover capire se la quarta lettera è corretta o meno, ha la necessità di ricordare quale
era il secondo simbolo letto, ovvero ha bisogno di memoria. La parola “radar” infatti
non è una stringa facente parte di un linguaggio regolare. È però appartenente alla
classe dei linguaggi liberi dal contesto, che sono riconosciuti dagli automi a pila.
4.1.2
Linguaggi context-free
I linguaggi context-free sono generati da una grammatica. Una grammatica non
è altro che un insieme di regole, dette produzioni, che indicano come generare un
linguaggio. Supponiamo di voler descrivere formalmente una semplice frase: essa
sarà composta da un soggetto e da un predicato.
f rase := soggetto predicato
(4.1)
La produzione dell’esempio è composta dai simboli denominati frase, soggetto, predicato. Accostiamo ora alla precedente le seguenti due produzioni, ove leggiamo |
32
4. Architettura del compilatore
come “oppure”:
soggetto := “Alice′′ |“Bob′′
(4.2)
predicato := “legge′′ |“scrive′′
(4.3)
Applicando le produzioni otteniamo cosı̀ quattro possibili frasi e precisamente “Alice
legge”, “Alice scrive”, “Bob legge”, “Bob scrive”. Queste ultime quattro frasi sono
definite come il linguaggio generato dalla grammatica. Osservando le produzioni date, possiamo notare che la (4.1) ha, molto informalmente, la proprietà di “portarci”
ad altre produzioni, mentre la (4.2) e la (4.3) ci informano che soggetto e predicato
sono dei simboli che possono assumere solo ben precisi valori. La (4.1) definisce
frase come un simbolo non terminale, mentre soggetto e predicato sono dei simboli terminali. Una grammatica, volendola definire formalmente, è una quadrupla
G = hV, S, T, P i, in cui:
• V è l’insieme dei simboli non terminali, altrimenti detti variabili
• S è il simbolo iniziale
• T è l’insieme dei simboli terminali
• P è un insieme di produzioni
Consideriamo ora il seguente insieme di produzioni:
B := 0
(4.4)
B := 1
(4.5)
B := (B and B)
(4.6)
B := (B or B)
(4.7)
B := (not B)
(4.8)
Esso è poco più complesso del precedente, ma vi appare qualcosa di nuovo, ovvero il
simbolo B anche a destra di alcune produzioni. Abbiamo cosı̀ introdotto una sorta
di ricorsione, ovvero l’elemento che da l’espressività in più ai linguaggi liberi dal
contesto rispetto ai linguaggi regolari. In questa grammatica si ha V = {B}, S =
B, T = {0, 1, and, or, not, (, )}. Essa genera tutte le possibili espressioni logiche.
4.2. Analisi Lessicale e Sintattica
4.2
33
Analisi Lessicale e Sintattica
Dopo questa breve e non rigorosa descrizione dei linguaggi formali, possiamo entrare
nei dettagli dei processi di analisi lessicale e sintattica, svolti dai moduli scanner.cpp
e parser.cpp.
4.2.1
Lo scanner
Il compito dello scanner è quello di trasformare in token il testo in input. Ogni
linguaggio di programmazione infatti è caratterizzato da sequenze di simboli che
hanno un ben preciso significato.
i f t e m p e r a t u r e < 2 0 . 5 then
power on heater ( ) ;
else
power off heater ( ) ;
end ;
Nel precedente esempio possiamo osservare un costrutto if-then-else: In esso compaiono le parole if, then, else ed end. Queste parole, che sono parole riservate,
fungono in un certo modo da “delimitatori” per le varie sezioni del costrutto. Inoltre, nel codice appaiono le espressioni temperature < 20.5, power on heater(); e
power off heater();. Nel testo tutti questi elementi sono semplici sequenze di caratteri, non comprensibili al parser. Lo scanner pertanto ha il compito di trasformarle
in “unità atomiche”. Lo spezzone di codice precedente è trasformato in qualcosa di
simile:
_if _identifier _lt _floatnumber _else
_identifier _lparen _rparen _semicolon
_else
_identifier _lparen _rparen _semicolon
_end _semicolon
A questo punto, la parola riservata if non è più una sequenza di caratteri, ma un
“segnaposto” per essa. Anche temperature, non è più la stringa che compare nel
testo, ma un token avente una proprietà “nome” uguale alla stringa “temperature”.
34
4. Architettura del compilatore
enum t o k e n s { i f , then ,
c l a s s Token
{
public :
Token ( t o k e n s type ) ; /∗
Token ( s t r i n g name ) ; /∗
Token ( i nt v a l u e ) ;
/∗
string
i nt
tokens
else ,
identifier ,
[ . . . ] };
C o s t r u t t o r e g e n e r i c o ∗/
C o s t r u t t o r e per un i d e n t i f i e r ∗/
C o s t r u t t o r e per un number ∗/
get name ( void ) ;
g e t v a l u e ( void ) ;
type ;
};
È abbastanza intuitivo vedere che tutte queste entità sono stringhe appartenenti ad
un linguaggio regolare. Lo scanner non è nient’altro che un automa a stati finiti
abbastanza complesso, ed il token è un “indicatore” dello stato di accettazione in
cui l’automa si è fermato. Ad esempio, per riconoscere un numero floating point si
può utilizzare l’automa di seguito rappresentato:
q0
q1
q2
q3
q4
q5
q6
q7
4.2.2
+
q1
q6
q1
q6
[0-9]
q2
q2
q2
q4
q4
q7
q7
q7
.
E
q3
q5
q5
Il parser
Precedentemente è stato accennato il fatto che il parser per portare a termine il proprio compito utilizza un algoritmo di parsing detto a discesa ricorsiva. L’obiettivo
del parser è quello di generare una struttura dati detta albero di sintassi astratta.
Supponiamo di voler eseguire il parsing del linguaggio generato dalla grammatica
data dalle (4.4), (4.5) e (4.8). Supponiamo inoltre di avere a disposizione uno scanner che quando chiamiamo la sua get token() ci restituisca i simboli f alse, true e
not. Lo pseudocodice di un possibile parser potrebbe essere il seguente:
4.2. Analisi Lessicale e Sintattica
35
Not
Not
True
Figura 4.1: Albero di sintassi astratta
ASTNode ∗ b o o l e a n e x p r e s s i o n ( void )
{
to ken t = s c a n n e r . g e t t o k e n ( ) ;
switch ( t )
{
case f a l s e :
return new F a l s e ( ) ;
case
true :
return new True ( ) ;
case
not :
ASTNode ∗ t h i s r o o t = new Not ( ) ;
thisroot . add child ( boolean expression ( ) ) ;
return t h i s r o o t ;
default :
p a r s i n g e r r o r ( ” Unexpected to ken ” ) ;
return NULL ;
}
}
i nt main ( void )
{
ASTNode∗ t r e e = b o o l e a n e x p r e s s i o n ( ) ;
}
Ovviamente, Not, True e False sono sottoclassi di ASTNode. Un simile parser,
chiamato su un’espressione che potrebbe essere not not 1, genererebbe un albero
simile a quello della Figura 4.1. L’idea sembra buona. Cerchiamo ora di introdurre
36
4. Architettura del compilatore
anche le due produzioni che avevamo precedentemente escluso, ovvero la (4.6) e la
(4.7), e modifichiamo il parser in accordo alla nuova grammatica.
ASTNode ∗ b o o l e a n e x p r e s s i o n ( void )
{
ASTNode ∗ l e f t s u b e x p r = b o o l e a n e x p r e s s i o n ( ) ;
to ken t = s c a n n e r . g e t t o k e n ( ) ;
switch ( t )
{
case f a l s e :
[...]
and :
ASTNode ∗ t h i s r o o t = new And ( ) ;
thisroot . add child ( left subexpr ) ;
thisroot . add child ( boolean expression ( ) ;
return t h i s r o o t ;
case o r :
[...]
case
default :
p a r s i n g e r r o r ( ” Unexpected to ken ” ) ;
return NULL ;
}
}
i nt main ( void )
{
ASTNode∗ t r e e = b o o l e a n e x p r e s s i o n ( ) ;
}
La prima istruzione di boolean expression è una chiamata a se stessa: questo causa
un loop infinito. Cosa è successo? E soprattutto, come risolviamo questo problema?
La grammatica data presenta delle produzioni in cui il simbolo B appare come primo
simbolo nella parte destra di alcune regole. Questa particolarità è chiamata ricorsione sinistra, e causa la non-terminazione del parser. Fortunatamente è possibile
rimuoverla in modo semplice, addirittura algoritmico, operando alcune modifiche
sulla grammatica. In [2] si dimostra che per ogni grammatica data è possibile ottenerne una equivalente senza ricorsione sinistra. La nostra nuova grammatica, una
volta eliminata la ricorsione sinistra, diventa:
booleanV alue =′′ 0′′ |′′ 1′′
(4.9)
booleanF act = booleanV alue|′′ not′′ booleanExpr
(4.10)
booleanExpr = booleanF act(′′ and′′ |′′ or ′′ )booleanExpr
(4.11)
4.2. Analisi Lessicale e Sintattica
Il nuovo parser potrebbe essere il seguente:
ASTNode∗ b o o l e a n f a c t o r ( void )
{
to ken t = s c a n n e r . g e t t o k e n ( ) ;
switch ( t )
{
case f a l s e :
return new F a l s e ( ) ;
case
true :
return new True ( ) ;
case
not :
ASTNode ∗ t h i s r o o t = new Not ( ) ;
thisroot . add child ( boolean expression ( ) ) ;
return t h i s r o o t ;
default :
p a r s i n g e r r o r ( ” Unexpected to ken ” ) ;
return NULL;
}
}
37
38
4. Architettura del compilatore
ASTNode∗ b o o l e a n e x p r e s s i o n ( void )
{
ASTNode∗ l e f t s u b e x p r = b o o l e a n f a c t o r ( ) ;
to ken t = s c a n n e r . g e t t o k e n ( ) ;
switch ( t )
{
case and :
ASTNode∗ t h i s r o o t = new And ( ) ;
thisroot . add child ( l e f t ) ;
thisroot . add child ( boolean expression ( ) ) ;
return t h i s r o o t ;
case
or :
ASTNode∗ t h i s r o o t = new Or ( ) ;
thisroot . add child ( l e f t ) ;
thisroot . add child ( boolean expression ( ) ) ;
return t h i s r o o t ;
default :
p a r s i n g e r r o r ( ” Unexpected to ken ” ) ;
return NULL ;
}
}
i nt main ( void )
{
ASTNode∗ t r e e = b o o l e a n e x p r e s s i o n ( ) ;
}
Si può facilmente intuire che questo secondo parser termina, restituendo l’albero
di sintassi astratta cercato. Ovviamente non è stata tenuta in considerazione la
precedenza delle operazioni, ma la si può codificare con uno sforzo minimo.
La tecnica a discesa ricorsiva è semplice ed efficace [11], [8], e ben si presta per
l’implementazione di prototipi di compilatori. Tuttavia, è poco flessibile, perché il
linguaggio riconosciuto da un parser cosı̀ scritto è “cablato” all’interno del codice
sorgente del parser stesso. I compilatori “di produzione” utilizzano algoritmi di
parsing guidati da tabelle. L’idea di fondo di tali algoritmi è che oltre al programma
da analizzare, anche le produzioni siano un input del parser [7], [1].
4.3
Analisi semantica
I controlli statici che questo compilatore implementa sono soltanto quelli strettamente necessari. La difficoltà implementativa di un’analisi statica “seria” non è affatto
elevata, infatti anch’essa è una sorta di visita ad alberi, ma è decisamente lunga.
4.4. Determinazione del tipo delle espressioni
39
Per questo si è deciso di ridurla al minimo. Ulteriori informazioni si possono trovare
in [7].
program s t a t i c c h e c k s ;
var x : integer ;
y : real ;
a : array 10 of r e a l ;
begin
x := y ;
y := x ;
a := x ;
a [ y ] := x ;
end .
L’analizzatore statico prevede tutti i casi mostrati nell’esempio di codice precedente.
Nel primo assegnamento si ha che, essendo x intero ed y reale, per poter eseguire l’operazione deve essere fatto un troncamento ad x. Viceversa, in y := x; il membro di
destra deve essere promosso a real perché l’assegnamento sia eseguito correttamente.
L’analisi semantica in queste circostanze informa il generatore di codice di emettere,
in corrispondenza del membro destro dell’assegnamento, l’opportuna istruzione di
conversione.
Il terzo comando richiede che la variabile x, che è di un tipo predefinito, venga assegnata ad una variabile di un tipo definito dall’utente: questo è un errore, ed in un
caso simile il compilatore termina senza produrre un eseguibile. Nel quarto caso si
tenta invece di utilizzare un numero reale come indice. Anche in questa situazione
viene segnalato un errore. Un indice reale infatti avrebbe ben poco senso.
4.4
Determinazione del tipo delle espressioni
Nel caso più complesso in cui si abbia qualcosa come
a[y] := 3*x+y;
si rende necessario capire che tipo di dato genera l’espressione a destra dell’assegnamento. Il compito non è difficile, infatti è sufficiente osservare la parte di albero di
sintassi astratta che rappresenta l’espressione. Tale sottoalbero è rappresentato in
Figura 4.2.
Una visita all’albero assegna ai nodi delle operazioni un attributo di tipo. Nel
caso delle operazioni matematiche quali addizione e prodotto, il tipo del risultato è il
40
4. Architettura del compilatore
ADD
MUL
3
type=integer
y
type=real
x
type=integer
Figura 4.2: Albero di sintassi astratta completo di informazione di tipo
tipo dell’operando “più ampio” coinvolto. Nell’esempio pertanto la moltiplicazione
ha come tipo di risultato un intero, mentre la somma un reale. Il tipo complessivo
dell’espressione per cui è real.
4.5
La tabella dei simboli
Nessuna delle fasi del compilatore può funzionare senza un luogo in cui poter memorizzare quanto scoperto durante l’analisi del programma dato in input. La struttura
più importante, oltre all’albero di sintassi astratta, è la tabella dei simboli.
Questa struttura dati è organizzata in modo gerarchico: i vari livelli rispecchiano
come sono innestate le funzioni all’interno del programma. Ogni livello punta ad
una serie di entry che rappresentano variabili, funzioni, costanti e tipi e contengono
tutti i dati che riguardano queste particolari entità. Ad esempio, una entry per una
funzione contiene il suo indirizzo, il numero ed il tipo dei parametri. A sua volta
ogni oggetto TabEntry (questo è il nome della classe all’interno del codice), punta
ad un oggetto Type, che rappresenta il tipo di dato dell’oggetto descritto dalla entry.
Anche Type è una struttura gerarchica, e questo è necessario a rappresentare i tipi
definiti dall’utente come record ed array.
La struttura dati mette a disposizione diverse operazioni:
• Enter
4.6. Generazione del codice
41
Figura 4.3: Tabella dei simboli
• Leave
• New
• Lookup
In breve, Enter e Leave servono a muoversi tra i vari livelli si scoping. New serve
per aggiungere una TabEntry allo scope corrente ed infine Lookup permette, dato
un nome, di risalire alla relativa TabEntry. Una corretta implementazione di questa
struttura dati e delle sue operazioni non è banale. Per ogni approfondimento si
rimanda a [7].
4.6
Generazione del codice
Nel capitolo introduttivo si è accennato molto informalmente al fatto che la generazione del codice è poco di più di una visita in post-ordine dell’albero di sintassi
astratta. I precedenti esempi di parser assumono che ogni entità di un programma di fatto un nodo dell’albero - sia rappresentata da un oggetto di un qualche sottotipo
di ASTNode. L’idea di fondo su cui si basa il generatore di codice di questo compilatore è quella di dotare la classe ASTNode di un metodo denominato generate(),
con il preciso compito di emettere il codice per una determinata sezione di programma. Ogni sottoclasse di ASTNode ridefinirà tale metodo in modo opportuno. Se
consideriamo il parser per le espressioni logiche visto nel paragrafo 4.2.2, i sottotipi
di ASTNode che ci sono necessari sono And, Or, Not, True e False. Ricordando che
stiamo compilando il codice per una macchina a stack, la generate() della classe
And potrebbe assomigliare a qualcosa del genere:
42
4. Architettura del compilatore
And
Or
True
True
False
Figura 4.4: Albero per l’espressione T rue or F alse and T rue
And : : g e n e r a t e ( )
{
ASTNode ∗ l e f t = c h i l d s . f i r s t ( ) ;
ASTNode ∗ r i g h t = c h i l d s . seco nd ( ) ;
l e f t −>g e n e r a t e ( ) ;
r i g h t −>g e n e r a t e ( ) ;
e m i t o p c o d e (AND) ;
}
Vale l’analogo per le classi Or e Not. Per quanto riguarda la classe True, che
rappresenta una costante, si potrebbe pensare a qualcosa di simile alla seguente
funzione:
True : : g e n e r a t e ( )
{
e m i t o p c o d e ( LDI true ) ;
}
Supponendo di avere l’espressione T rue or F alse and T rue, il parser genererebbe
un albero simile a quello in Figura 4.4 Per generare il codice è sufficiente chiamare generate() sulla radice. Quello che succede è che a cascata viene chiamata la
generate() di Or, ed in seguito quella di True. Quest’ultima emette LDI true. Al
ritorno, Or chiama il suo figlio destro, che emette LDI false. A questo punto si
ritorna di nuovo ad Or, che emette OR. Si ritorna cosı̀ ad And, che chiamando il suo
figlio destro emette LDI true. And infine emette AND. Quello che si è ottenuto è
l’equivalente in P-Code dell’espressione di partenza, ovvero:
4.7. Conclusioni
43
LDI true
LDI false
OR
LDI true
AND
Un’ottima trattazione sulla generazione del P-Code si può trovare in [7].
4.7
Conclusioni
Il campo dei compilatori è sconfinato: in questo capitolo si è voluto dare l’idea
generale di quello che è il funzionamento del compilatore scritto, che non è comunque
dissimile da quello di un compilatore “vero”, almeno per le prime fasi. Infatti, questo
compilatore innanzitutto non è ottimizzante: una fase di ottimizzazione è facilmente
integrabile, ma oltre a non rientrare tra gli obiettivi del lavoro, avrebbe richiesto
troppo tempo per essere scritta. Inoltre, questo compilatore produce codice per una
macchina a stack: questa è una semplificazione notevole. Intuitivamente, quello che
succede è che non viene svolta la fase di traduzione da codice intermedio a codice
macchina. Questa fase si dovrebbe occupare di gestire una notevole quantità di
dettagli relativi al processore per cui si vuole generare il codice, alcuni dei quali non
sono semplici, ad esempio l’allocazione dei registri.
Una trattazione di base sui compilatori si può trovare in [11], mentre una trattazione più completa la si può trovare in [7]. La bibbia in fatto di compilatori, testo
che richiede un certo impegno, è [1].
44
4. Architettura del compilatore
5
Tecniche di analisi volte alla
parallelizzazione automatica
5.1
Analisi delle dipendenze
Il semplice susseguirsi delle istruzioni in un programma comporta che si instaurino
tra loro alcuni tipi di dipendenze. Non rispettare queste dipendenze ha come risultato un cambiamento di significato del programma. È perció chiaro che, se vogliamo
eseguire in modo parallelo un programma, è necessario che tali vincoli vengano rispettati pienamente. Le problematiche presentate di seguito sono ben conosciute ai
progettisti di CPU nell’ambito delle pipeline e dell’esecuzione fuori ordine, tecniche
volte alla massimizzazione delle prestazioni raggiungibili da un determinato chip
[10]. L’analisi delle dipendenze per cui è una tecnica di analisi del codice che è in
grado di produrre dei vincoli tra le istruzioni di un programma [4], [5]. Essa è necessaria a determinare se è possibile ri-ordinare o, più in generale, eseguire in un ordine
arbitrario, anche contemporaneamente, una sequenza di comandi senza cambiare il
significato del programma, o senza fargli assumere comportamenti imprevisti.
5.1.1
Dipendenze sui dati
In tutto possiamo osservare i seguenti tipi di dipendenze sui dati: [6]
• Dipendenza Read After Write, o Flow-dipendenza
• Dipendenza Write After Read, o Antidipendenza
• Dipendenza Write After Write, o Output-dipendenza
• Dipendenza Read After Read, o Input-dipendenza
46
5. Tecniche di analisi volte alla parallelizzazione automatica
Dipendenza di flusso
Consideriamo il seguente frammento di codice:
x := 1 2 3 4 ;
y := x + 1 ;
Nella prima riga di codice assegnamo alla variabile x il valore 1234, mentre nella
seconda riga alla variabile y viene assegnato il valore di x incrementato di uno.
Supponiamo ora che il grado di parallelismo che abbiamo a disposizione sia al livello
della singola istruzione; in altre parole supponiamo che le due righe di codice possano
venire eseguite assieme: si osserva immediatamente che per eseguire la seconda
istruzione è necessario conoscere il valore di x, calcolato dalla prima. Si deduce
perció che le due istruzioni devono essere eseguite una di seguito all’altra, cosı̀ come
sono scritte, onde evitare di leggere un valore non aggiornato di x. La dipendenza
che nasce è definita Read After Write, in breve RAW, oppure Flow-dipendenza,
ricordando che il dato x deve fluire dalla prima istruzione alla seconda. Siano per
cui C1 e C2 comandi: essi sono flusso-dipendenti se e solo se C1 modifica una risorsa
che C2 legge e C1 precede C2 in esecuzione, e si indica nel seguente modo:
C1 δf C2
Antidipendenza
L’antidipendenza è l’esatto inverso della dipendenza di flusso. Siano per cui C1 e C2
comandi: essi sono antidipendenti se e solo se C2 modifica una risorsa che C1 legge
e C1 precede C2 in esecuzione, e si indica nel seguente modo:
C1 δa C2
Un semplice frammento di codice che presenta tale tipo di dipendenza è il seguente,
esatto speculare del precedente:
y := x + 1 ;
x := 1 2 3 4 ;
Il significato dell’antidipendenza è il seguente: la prima istruzione necessita di leggere
x, ma se permettiamo che il loro ordine venga invertito, otteniamo una non corretta
lettura di x, da cui il nome Write After Read.
5.1. Analisi delle dipendenze
47
Output-dipendenza
Questo terzo tipo di dipendenza è generato da due scritture consecutive dello stesso
elemento. Se infatti prendiamo in considerazione le istruzioni:
x := 1 2 3 ;
x := 4 5 6 ;
otteniamo che, se non eseguite nell’esatto ordine in cui sono scritte, all’uscita della
sezione di codice che le contiene otteniamo un valore errato per x. La dipendenza
per cui si genera nel momento il cui due comandi C1 e C2 modificano la stessa risorsa
e C1 viene eseguito prima di C2 . L’output-dipendenza è definita anche dipendenza
Write After Write, ed è indicata nel seguente modo:
C1 δo C2
Input-dipendenza
L’input-dipendenza, pur non essendo propriamente una dipendenza, si verifica nel
caso due istruzioni leggano lo stesso dato:
y := x + 1 2 3 ;
z := x + 4 5 6 ;
Tale tipo di dipendenza, se cosı̀ si può chiamare, non impone un particolare ordine
di esecuzione trattandosi di sole letture, ed è indicata nel seguente modo:
C1 δi C2
Altre considerazioni sulle dipendenze
Dei tipi di dipendenza finora presentati, soltanto la dipendenza di flusso è una dipendenza non eliminabile. Le altre dipendenze nascono dal fatto che le variabili
coinvolte sono considerate come locazioni di memoria, e non come un puro valore. In svariati casi infatti sono eliminabili rinominando le variabili coinvolte. Le
dipendenze sui dati stabiliscono un ordine parziale sui comandi che utilizzano i dati
oggetto delle dipendenze.
48
5. Tecniche di analisi volte alla parallelizzazione automatica
5.1.2
Dipendenze sui cicli
La parallelizzazione dei cicli di un programma è un’ottima idea ai fini della computazione parallela. Il problema nel caso dei cicli si pone nel momento in cui un’iterazione dipende dalla successiva. Vediamo innanzitutto un ciclo che non crea particolari
problemi ai fini della parallelizzazione:
begin
for i := 0 to n do
a[ i ] = b[ i ] + c [ i ];
end ;
end .
In un caso simile è evidente che anche se tutti i cicli dovessero essere eseguiti parallelamente il risultato del programma non cambierebbe, anzi, si avrebbe uno speed-up
teoricamente pari ad n.
begin
for i := 0 to n do
a [ i ] = b [ i −1] + c [ i ] ;
end ;
end .
Una piccola modifica come quella effettuata nel codice precedente già vanifica molti
sforzi volti a parallelizzare un ciclo.
5.1.3
Dipendenze sul controllo
Supponiamo di avere il seguente frammento di codice:
begin
b := 2 ;
i f a = 0 then
b = 3;
end ;
write ( b ) ;
end .
L’esecuzione del comando b := 3 (chiamiamolo C2 ) è condizionata alla verità della
condizione del comando if (chiamiamolo C1 ). In altre parole C2 è control-dipendente
da C1 o, in simboli:
C1 δc C2
5.2. Analisi dei dati utilizzati dal codice
5.2
49
Analisi dei dati utilizzati dal codice
Alla luce di quanto detto finora sulle dipendenze sui dati, possiamo rivedere il tutto
da una prospettiva più macroscopica, ovvero quella delle funzioni. Un’idea molto
semplice per parallelizzare un programma è infatti cercare di capire, analizzandolo,
quali siano i dati effettivamente utilizzati dalle varie sezioni di codice, le funzioni, in
esso presenti. Esaminiamo il seguente frammento:
program prova1 ;
var a : array 10 of integer ;
var b : array 10 of integer ;
begin
quicksort(a );
quicksort (b ) ;
end .
Tralasciando alcuni dettagli quali l’inizializzazione dei vettori e ammettendo che
la funzione quicksort prenda il suo parametro per riferimento, e che utilizzi per i
suoi scopi solo il parametro stesso, possiamo senz’altro eseguire le due chiamate in
parallelo, senza preoccuparci che vi siano interferenze non volute, ed essendo sicuri
di ottenere il risultato corretto. Cerchiamo ora di ragionare in modo più formale sul
problema.
5.2.1
Condizioni di Bernstein
Supponiamo di analizzare il seguente frammento di codice, composto da due semplici
procedure:
program prova2 ;
var x : integer ;
var y : integer ;
procedure f ;
begin
x := 5 ;
end ;
procedure g ;
begin
y := 6 ;
end ;
begin
f ();
g ();
end .
50
5. Tecniche di analisi volte alla parallelizzazione automatica
Definiamo Rf l’insieme delle variabili che vengono lette dalla funzione f , e,
analogamente, Wf l’insieme delle variabili che vengono scritte dalla stessa funzione
f . Relativamente al programma in questione, otteniamo che per f si ha Rf = ∅ e
Wf = {x}, mentre, per quanto riguarda g, si ha Rg = ∅ e Wg = {y}. Osserviamo che
se le due funzioni non scrivono gli stessi dati, possono essere eseguite in parallelo.
Diciamo per cui che, date due funzioni f e g, la loro esecuzione parallela f kg è
equivalente alla loro esecuzione sequenziale f, g se l’intersezione dei loro insiemi di
scrittura è vuota. In simboli:
f kg ≡ f, g ⇒ Wf ∩ Wg = ∅
(5.1)
Se non teniamo in considerazione questa condizione, modificando g nel seguente
modo sorge un problema:
procedure g ;
begin
x := 6 ;
end ;
Se eseguiamo in parallelo f e g incorriamo in una race condition, in quanto il valore
di x sarà dipendente dal momento in cui le due funzioni vengono eseguite. La (5.1)
esprime nient’altro che una dipendenza Write After Write tra f e g, ovvero che
f δo g.
È tuttavia abbastanza banale accorgersi del fatto che la (5.1) non è una condizione sufficiente. Per evidenziare ciò basta modificare una delle due funzioni,
supponiamo f , nel seguente modo:
procedure f ;
begin
x := 5 + y ;
end ;
da cui si ottiene che Rf = {y} e Wf = {x}, mentre per g la situazione rimane
Rg = ∅ e Wg = {y}. Ci si trova cosı̀ in una situazione di antidipendenza e si ottiene:
f kg ≡ f, g ⇒ Rf ∩ Wg = ∅
(5.2)
Agendo analogamente su g si può arrivare ad una dipendenza di flusso, da cui:
5.2. Analisi dei dati utilizzati dal codice
51
f kg ≡ f, g ⇒ Wf ∩ Rg = ∅
(5.3)
Le tre condizioni appena trattate si riassumono in:


Wf ∩ Wg = ∅
f kg ≡ f, g ⇔ Rf ∩ Wg = ∅


Wf ∩ Rg = ∅
(5.4)
e sono chiamate condizioni di Bernstein.
52
5. Tecniche di analisi volte alla parallelizzazione automatica
6
Descrizione del lavoro svolto
6.1
Idea generale
Il capitolo precedente mostra alcune tecniche utili a cercare il parallelismo in un programma. In particolare, permettono di capire se vi sono parti di codice che possono
essere eseguite parallelamente, senza cambiare il significato del programma stesso.
Queste tecniche ben si adattano ai multiprocessori a memoria condivisa, anzi, danno buoni risultati, mentre creano notevoli overhead di comunicazione su macchine a
memoria distribuita.
L’approccio che abbiamo deciso di seguire per strutturare il meccanismo distribuito
è essenzialmente diverso perché si vuole evitare di dover trasferire troppi dati, al
fine di non abbattere le prestazioni invece che migliorarle. Quanto presentato sono
alcune tecniche alla base di uno strumento che, dato un programma sequenziale,
supporti la multiprogrammazione rilevando le sezioni di codice indipendenti all’interno del codice dato e ponendo queste in diverse unità di calcolo, assicurandosi
che la comunicazione tra le unità sia ridotta al minimo. L’approccio non è quello
di “parallelizzare” il codice: esso rimane puramente sequenziale. Il vantaggio lo
si ottiene nel momento in cui vengono lanciati più programmi compilati nel modo
proposto. L’effetto complessivo è quello che l’insieme dei processi in esecuzione trae
beneficio da tutte le risorse di calcolo disponibili. Si può osservare un’idea simile in
MOSIX: in tal caso la granularità è a livello di processo, mentre nel caso del sistema
presentato la granularità è a livello di funzione. Si pensi ad esempio al programma
di Figura 6.1:
È facile osservare che è possibile rendere indipendenti le due procedure dichiarate. Per un simile frammento di codice, vengono generati 3 eseguibili, uno per il
“main”, uno per do_something_on_a ed uno per do_something_on_b. Il risultato
è che le due chiamate nel “main” diventano remote, e la loro esecuzione avviene su
54
6. Descrizione del lavoro svolto
program example ;
var a : array 20 of integer ;
var b : array 20 of integer ;
procedure d o s o m e t h i n g o n a ( ) ;
var i ;
begin
i = 0;
while i < 20 then
begin
a[ i ] = i ;
end ;
end ;
procedure d o s o m e t h i n g o n b ( ) ;
var i ;
begin
i = 0;
while i < 20 then
begin
b[ i ] = i ;
end ;
end ;
begin
do something on a ( ) ;
do something on b ( ) ;
end .
Figura 6.1: Esempio di programma che contiene funzioni separabili
6.2. Modifiche al compilatore
55
macchine virtuali presenti su unità di elaborazione potenzialmente diverse da quella
del chiamante. L’idea generale è pertanto:
• avere un compilatore che implementi delle tecniche che identificano sezioni di
codice che non condividono dati e le compili su eseguibili differenti
• avere un ambiente run-time, ovvero una virtual machine, che esegua il codice
compilato in questo modo, mettendo a disposizione dei meccanismi di chiamata di procedura remota.
Il problema principale che si pone è che ogni funzione, per poter essere eseguita,
ha bisogno di avere sullo stack l’ambiente corretto su cui operare. Ogni macchina
virtuale pertanto, durante l’inizializzazione deve eseguire del codice opportuno per
ricreare i frame con la stessa struttura che avrebbero nel caso “non distribuito”, ma
senza allocare le variabili inutili, e poi portarsi in una condizione di “wait” in cui attende le chiamate delle macchine virtuali remote. Affinché si possa ottenere qualcosa
di simile è necessario introdurre delle semplici analisi all’interno del compilatore, che
di seguito sono presentate.
6.2
Modifiche al compilatore
Per decidere se sia possibile o meno “separare” delle sezioni di codice è innanzitutto
necessario capire quali dati esse utilizzano. Questo non è un compito semplice, e, per
mantenere bassa la complessità del prototipo da sviluppare, sono state introdotte
alcune limitazioni:
• Non è ammesso il passaggio per riferimento
• Nel caso di array o record, questi sono considerati come “atomici”: se due
funzioni accedono ad esempio a membri diversi di un record, esse non vengono
separate.
Nel caso del passaggio per riferimento o dei record rimane decidibile staticamente quali dati vengano effettivamente utilizzati; cosı̀ non è invece, a meno di casi
particolari, nel caso di array e puntatori.
6.2.1
Le relazioni uses e usedby
Per decidere quali funzioni siano separabili, vengono costruite due relazioni, denominate rispettivamente uses (U) ed usedby (V). Entrambe vengono calcolate a partire
56
6. Descrizione del lavoro svolto
program prova ;
var x , y , z : integer ;
procedure f ( ) ;
begin
x := 3 ;
end f ;
procedure g ( ) ;
begin
x := 4 ; y := 5 ;
end g ;
procedure h ( ) ;
begin
y := 6 ;
end h ;
procedure k ( ) ;
begin
z := 7 ;
end k ;
begin
f (); g (); h(); k();
end prova .
Figura 6.2: Programma con cluster non banali
da relazioni precedentemente generate. Tali relazioni sono declares (D), reads (R),
writes (W), nonlocal reads (N R) e nonlocal writes (N W). Le relazioni ovviamente
coinvolgono le funzioni e le variabili che esse utilizzano. Nel listato precedente ad
esempio si ha che do_something_on_b declares(i), reads(i) e writes(b). Vediamone
i dettagli.
D viene calcolata al momento del parsing. Ad ogni dichiarazione di variabile, la
variabile viene aggiunta a D.
R viene calcolata nello stesso momento, e fanno parte di essa tutti gli identificatori utilizzati come r-valori, ovvero gli identificatori che si trovano a destra di
un’espressione oppure ad indice di un array.
Assieme ad R viene calcolata anche W, e di essa fanno parte tutti gli identificatori
utilizzati come l-valori, ovvero gli identificatori che che compaiono a sinistra di un
assegnamento.
N R altro non è che R \ D ed analogamente N W è data da W \ D. Ad esempio,
in riferimento al programma di Figura 6.2, vengono calcolate le seguenti relazioni:
6.2. Modifiche al compilatore
57
• Per lo scope globale: Dprova = x, y, z, Rprova = ∅, Wprova = ∅
• Per f : Df = ∅, Rf = ∅, Wf = {x}
• Per g: Dg = ∅, Rg = ∅, Wg = {x, y}
• Per h: Dh = ∅, Rh = ∅, Wh = {y}
• Per k: Dk = ∅, Rk = ∅, Wk = {z}
Per capire quali sezioni di codice sia possibile separare serve sapere se esistono
funzioni che utilizzano le stesse variabili, pertanto viene calcolata U = N R ∪ N W.
Affinché due funzioni f1 ed f2 siano separabili, si deve avere che Uf1 ∩ Uf2 = ∅. Nel
caso del programma di Figura 6.2, dalla definizione della relazione U si ottiene che:
• Per lo scope globale: Uprova = ∅
• Per f : Uf = {x}
• Per g: Ug = {x, y}
• Per h: Uh = {y}
• Per k: Uk = {z}
mentre dalla definizione di V si ottiene che:
• Per x: Vx = {f, g}
• Per y: Vy = {g, h}
• Per z: Uz = {k}
V, a differenza delle precedenti relazioni, associa variabili a funzioni anziché
funzioni a variabili. In altre parole, V rappresenta “cosa è utilizzato da chi”. U e V,
tramite l’operazione di join, permettono di calcolare i gruppi di funzioni cercati, che
denominiamo cluster. Un cluster pertanto è un insieme di funzioni che metteremo
in un singolo processo.
Una volta ottenuti i cluster, si provvede ad assegnare ad ogni funzione l’indice del
cluster a cui appartiene. Altrettanto si fa con le variabili. Questa ultima operazione
sulle variabili ha come effetto collaterale il calcolo dei loro offset all’interno del frame
corrispondente, che vengono cosı̀ memorizzati sulla tabella dei simboli.
58
6. Descrizione del lavoro svolto
6.2.2
Operazione di join
La definizione di join è abbastanza intricata, ma l’idea su cui si basa è molto semplice. Data una funzione f , si va a vedere quali variabili utilizza tramite U. Se U
ci informa che f utilizza a e b, allora tramite V si risale a quali funzioni utilizzano
le stesse variabili, e le si fanno appartenere allo stesso cluster di f . Ripetendo il
procedimento per ogni funzione definita in un programma, si ottiene l’insieme di
tutti i cluster.
Siano f1 , . . . , fn tutte le funzioni presenti in un dato programma P , e sia Sfi
con 1 ≤ i ≤ n il cluster che contiene soltanto l’i-esima funzione. Sia inoltre S =
{S1 , . . . , Sn } l’insieme di tutti i cluster. L’operazione di join è cosı̀ definita:
for all f ∈ P do
for all v ∈ Uf do
for all (g 6= f ) ∧ (g ∈ Vv ) do
S ← S \ {Sf , Sg } ∪ (Sf ∪ Sg )
Un prerequisito per l’esecuzione di join è che ogni funzione appartenga ad un cluster che contiene solo essa. Pertanto, eseguendo l’operazione sulle relazioni ottenute dal programma in Figura 6.2 prima di join si avrà l’insieme di cluster S =
{S0 , S1 , S2 , S3 }, ed in particolare S0 = {prova}, S1 = {f }, S2 = {g}, S3 = {h}
e S4 = {k}. Ora, per ogni funzione definita nel programma si va a vedere quali
variabili usa.
• prova: Uprova = ∅, pertanto si passa alla funzione successiva.
• f : Uf = x. Da Vx si deduce che x è utilizzata anche da g, pertanto S1
ed S2 collassano in un singolo cluster. La situazione ora è: S0 = {prova},
S1 = {f, g}, S2 = {h} e S3 = {k}.
• g: Ug = x, y. Da Vy si deduce che y è utilizzata anche da h, e anche in questo
caso si verifica che S1 ed S2 collassano. Si ha che: S0 = {prova}, S1 = {f, g, h}
e S2 = {k}
• h: Non si deduce nulla di nuovo.
• k: Di nuovo, non si deduce altro. Non vi sono ulteriori funzioni definite nel
programma e l’algoritmo termina con S = {{prova}, {f, g, h}, {k}}.
Il codice che implementa la costruzione di U e V, assieme alla funzione join si trova
nel modulo analysis.cpp.
6.2. Modifiche al compilatore
59
main
rank = 0
a
rank = 1
b
rank = 2
statement
sequence
statement
sequence
statement
sequence
call a
call b
Figura 6.3: Albero con le informazioni relative ai cluster
6.2.3
Numerazione delle funzioni
Subito dopo l’esecuzione di join quello che si ottiene è un certo numero di cluster. Il
cluster che contiene il “main” è il numero 0, gli altri sono numerati progressivamente.
Ad ogni nodo dell’albero di parsing che rappresenta una funzione, ovvero ai nodi di
tipo Procedure viene assegnato il numero del cluster a cui appartiene. In riferimento
al programma precedente, si ha una situazione del genere:
Durante la fase di generazione del codice il compilatore mantiene diversi stream:
gli stream non sono niente altro che il bytecode che verrà inserito nei diversi eseguibili. Affinché il compilatore inserisca il bytecode nello stream corretto, la generate()
dei nodi di tipo Procedure è qualcosa di simile al seguente pseudo-codice:
P r o cedur e : : g e n e r a t e ( )
{
f o r e a c h ( c o f type P r o cedur e i n c h i l d s )
c . generate ( ) ;
prev rank = get stream ( ) ;
s e t s t r e a m ( rank ) ;
my body . g e n e r a t e ( ) ;
set stream ( prev rank ) ;
}
60
6. Descrizione del lavoro svolto
Gli stream ottenuti in questo modo, in riferimento al programma in Figura 6.1, sono
cosı̀ formati:
main
ENT 160
MST
CUP do ... a
MST
CUP do ... b
do_something_on_a
ENT 4
LDA 0, 10
LDI 0
STO
[...]
LDA 1, 0
LDA 0, 10
LOD
IXA 4
[...]
do_something_on_b
ENT 4
LDA 0, 10
LDI 0
STO
[...]
LDA 1, 80
LDA 0, 10
LOD
IXA 4
[...]
È immediato osservare che il codice di do_something_on_a e di do_something_on_b
ha un problema: l’istruzione che carica l’indirizzo dell’array a cui si vuole accedere,
LDA 1, 80 nello stream di do_something_on_b, genera un riferimento in memoria
non valido. Nello stream di do_something_on_a è corretta, ma questo è solo frutto
del caso. Questo problema deve essere risolto, e la fase successiva del compilatore
ha proprio questo compito.
6.2.4
Numerazione delle variabili ed allocazione
Questa seconda fase, come già visto, è necessaria per far in modo che al momento
dell’esecuzione il codice presente nei vari stream possa avere il corretto ambiente su
cui girare. L’idea è di emettere del codice aggiuntivo che ricrei sullo stack l’ambiente
che le funzioni del cluster si aspettano. Per questo motivo anche le variabili vengono
numerate, sempre in base al cluster a cui appartengono. Vediamo l’algoritmo.
Sia ofs(v ) l’offset della variabile v e sizeof (v ) la dimensione del tipo di dato di
v. Sia inoltre level(P ) il livello di annidamento della procedura P. Come visto in
precedenza, le variabili vengono allocate sullo stack, subito dopo le informazioni
relative alle catene statiche e dinamiche e al valore ed indirizzo di ritorno. Questo
comporta che ogni variabile abbia un offset rispetto all’inizio del frame. L’ultima
variabile allocata si troverà all’indirizzo i: la successiva dovrà essere posizionata
all’indirizzo i + sizeof (v ). Sia tale posizione nextof s.
1. Inizialmente qualunque variabile appartiene al cluster -1
2. Per ogni procedura P
(a) Per ogni variabile v ∈ UP , il cluster di v diventa quello di P
6.2. Modifiche al compilatore
61
(b) Per ogni variabile v ∈ DP , se è un parametro viene saltata, come pure se
non appartiene allo stesso cluster di P. Altrimenti, se il suo cluster è lo
stesso di P, allora ofs(v ) = nextofs e nextofs = nextofs + sizeof (v ). Alla
fine di questo passo nextof s contiene il valore con cui eseguire ENT per P.
Tutte queste informazioni vengono mantenute nella tabella dei simboli.
(c) Per ogni variabile v ∈ DP , se appartiene allo stesso cluster di P è già
stata considerata per cui va saltata, come pure se è un parametro. Nel
caso in cui appartenga ad un cluster diverso da quello di P, diciamo il
cluster s, allora essa va allocata al livello level(P ) del cluster s.
Si noti come nel passo 2c s possa essere -1. Questo succede nel caso v non sia
utilizzata, e anche in tal caso la variabile va saltata: questo algoritmo ha il sideeffect di escludere dall’allocazione eventuali variabili non utilizzate. Il risultato che
con questo algoritmo si ottiene è il seguente:
main
MST
CUP
MST
CUP
do_..._a
do_..._b
do_something_on_a
ENT
80
MST
ENT
4
LDA
0, 10
LDI
0
STO
[...]
LDA
1, 0
LDA
0, 10
LOD
IXA
4
[...]
do_something_on_b
ENT
80
MST
ENT
4
LDA
0, 10
LDI
0
STO
[...]
LDA
1, 0
LDA
0, 10
LOD
IXA
4
[...]
Vediamone l’esecuzione sul programma in Figura 6.2. Tramite il passo 2a, viene
deciso che x ed y appartengono al cluster 1, mentre z appartiene al cluster 2. Questa
informazione viene mantenuta nell’entry della tabella dei simboli relativa ad ogni
variabile.
Il passo 2b si occupa di calcolare gli offset delle variabili locali delle funzioni,
e di conseguenza la quantità di spazio necessaria ad ognuna (la quantità da utilizzare come argomento di ENT). È indispensabile mantenere questo passo separato
dal precedente. Infatti, se fusi, durante l’allocazione dei dati di una certa funzione alcune variabili potrebbero non essere ancora state numerate, e di conseguenza
l’informazione necessaria al calcolo degli offset non sarebbe sufficiente.
Infine, il passo 2c alloca, analogamente al 2b le variabili non locali. Ad esempio,
è in questo passo che x, y e z vengono allocate ai blocchi 1 e 2.
62
6. Descrizione del lavoro svolto
Grazie a questo procedimento ogni macchina può eseguire il codice correttamente, e avendo ricalcolato opportunamente gli indirizzi anche il problema dei riferimenti è risolto. Manca però da capire come far si che le macchine che hanno in
carico do_something_on_a e do_something_on_b “aspettino” di essere chiamate
dal “main”.
Da notare che il compilatore in una situazione analoga al frammento seguente
non genera codice corretto:
program i n c o r r e c t ;
var x , y : integer ;
procedure f ( ) ;
procedure g ( ) ;
begin
x := 1 ;
y := 2 ;
end ;
begin
end f ;
begin
x := 3 ;
end i n c o r r e c t .
In termini più astratti, data una funzione a livello di scoping n, se essa non
utilizza dati del livello n − 1 ma utilizza dati del livello n − 2, e la funzione a livello
n − 1 non utilizza dati a livello n − 2, l’ambiente che la procedura a livello n trova al
momento dell’esecuzione non è corretto. Questa limitazione è dovuta a problemi di
tempo. Tecnicamente è causata dal modo in cui è tenuta traccia dei valori di ENT
dei vari livelli di scoping. Eliminarla non richiede un grande sforzo.
6.3
Modifiche all’ambiente runtime
L’esecuzione distribuita del codice ottenuto deve essere in qualche modo coordinata,
e per questo si sono rese necessarie delle modifiche alla macchina virtuale.
• Aggiunta dell’istruzione WAIT
• Modifica del comportamento di CUP
• Modifica del comportamento di RET
L’istruzione WAIT serve per portare la macchina virtuale in una sorta di stato di
attesa, dove essa attende che le vengano inviate le informazioni per poter iniziare ad
6.3. Modifiche all’ambiente runtime
63
eseguire la parte di codice ad essa assegnata.
CUP è stata modificata, nel caso che la chiamata da eseguire sia ad una funzione
remota, in modo da poter interagire con una macchina in condizione di wait, mentre
RET ha il compito aggiuntivo di riportare la macchina in wait dopo essere stata
chiamata da remoto.
6.3.1
Istruzione WAIT
Nella tabella precedente, si vede come agli stream di do_something_on_a e di
do_something_on_b siano state aggiunte le istruzioni ENT e MST all’inizio del
codice. Queste istruzioni fanno parte di quello che è stato definito lo stub di inizializzazione. Lo stub non fa altro che quello che ci eravamo proposti, ovvero ricostruire
la parte di stack necessaria. Una volta che lo stub è stato eseguito però la VM deve
fermarsi in attesa di istruzioni. Per questo motivo, subito dopo di esso, viene emessa
l’istruzione WAIT. Il suo pseudocodice è il seguente ed è di immediata comprensione.
while ( PC < p r o g r a m l e n g t h )
{
instruction inst = fetch ( );
switch ( i n s t )
{
[...]
case WAIT:
MPI Recv ( a d d r t o c a l l ) ;
MPI Recv ( p a r a m e t e r s ) ;
mark stack for remote return ( ) ;
put o n sta ck ( parameters ) ;
PC = a d d r t o c a l l ;
break ;
[...]
}
}
WAIT marca lo stack con un magic number nella posizione in cui andrebbe posizionato l’indirizzo di ritorno. Il magic number vero e proprio sono i 2 byte più significativi del return address, mentre il byte meno significativo indica a quale macchina
inviare il valore di ritorno della funzione eseguita, e di conseguenza a quale macchina
far riprendere il controllo. In mancanza di un simile accorgimento, MPI Send non
potrebbe sapere a chi inviare il messaggio di return.
64
6. Descrizione del lavoro svolto
6.3.2
Istruzione CUP
CUP nella versione non distribuita dell’ambiente runtime prevede come operando un
indirizzo a 32 bit, che specifica l’entry point della funzione chiamata. Nella versione
distribuita, sono stati sacrificati gli 8 bit più significativi dell’indirizzo passato a
CUP, al fine di poter inserire al loro posto l’indice del cluster a cui appartiene la
funzione da chiamare. Questo indice si traduce, nella terminologia MPI, nel rank
della VM che sta per essere chiamata.
La versione di CUP non distribuita è qualcosa di simile a quanto segue:
while ( PC < p r o g r a m l e n g t h )
{
instruction inst = fetch () ;
switch ( i n s t )
{
[...]
case CUP:
adjust MP ( ) ;
PC = g e t c u p a r g u m e n t ( ) ;
break ;
[...]
}
}
La versione distribuita invece prevede il caso di chiamata remota:
6.3. Modifiche all’ambiente runtime
65
while ( PC < p r o g r a m l e n g t h )
{
instruction inst = fetch ( );
switch ( i n s t )
{
[...]
case CUP:
adjust MP ( ) ;
m a c h i n e t o c a l l = ( g e t c u p a r g u m e n t ( ) >> 2 4 ) & 0xFF ;
a d d r e s s t o c a l l = g e t c u p a r g u m e n t ( ) & 0xFFFFFF ;
i f ( m a c h i n e t o c a l l != me)
{
MPI Send ( a d d r e s s t o c a l l , m a c h i n e t o c a l l ) ;
MPI Send ( pa r a meter s , m a c h i n e t o c a l l ) ;
MPI Recv ( r e t u r n v a l u e ) ;
put on stack ( return value ) ;
}
else
PC = a d d r t o c a l l ;
break ;
[...]
}
}
6.3.3
Istruzione RET
L’istruzione RET, nella sua versione di base non fa nulla altro che ripristinare MP e
distruggere il frame della funzione appena eseguita. Nel caso debba essere eseguito
un remote return, oltre a fare ciò, RET deve inviare il return value alla macchina
chiamante e riportare la propria macchina virtuale in condizione di WAIT, in modo
che possa rispondere ad una successiva richiesta di esecuzione.
66
6. Descrizione del lavoro svolto
Conclusioni
Il lavoro svolto consiste in una implementazione per il linguaggio Pascal pensata per
sfruttare le caratteristiche di un ambiente distribuito. Lo scopo, in particolare, è stato quello di gettare le basi di uno strumento che potesse in qualche modo supportare
il programmatore evitando di dover scrivere appositamente software per macchine a
memoria distribuita. L’idea di base è stata quella di identificare automaticamente
delle sezioni di codice che non condividono dati, per poi porle su unità di calcolo
differenti. Un meccanismo di call/return remoti fa si che il flusso del programma
si articoli su diverse CPU invece che su una sola. L’approccio adottato non porta
benefici al singolo programma in esecuzione: una call remota infatti è bloccante
dal lato della macchina che la esegue. Questo implica che l’esecuzione del singolo
programma rimanga strettamente seriale. Nella quasi totalità dei casi però, su un
elaboratore si vuole eseguire diversi processi, i quali sono potenzialmente composti
da più sezioni, distribuite su più CPU. L’esecuzione concorrente di un certo numero
di processi cosı̀ compilati trae perciò beneficio in modo trasparente da hardware a
memoria distribuita.
Quanto proposto è stato implementato ed è disponibile all’indirizzo internet
http://sourceforge.net/projects/opc. Il software si pone l’obiettivo di essere un
proof-of-concept piuttosto che un tool interamente funzionante. Durante l’implementazione, per ragioni principalmente dettate dai tempi, si è persa di vista l’architettura generale del compilatore di base, e sono state introdotte alcune inconsistenze,
compromettendo la mantenibilità. Pertanto, ogni ulteriore miglioramento andrebbe sviluppato su una riscrittura del software progettata tenendo conto di quanto
appreso scrivendo questa “versione 0”.
Di seguito sono proposte due possibili estensioni del lavoro proposto.
Scheduler Come già illustrato, per lo strato di comunicazione è stata utilizzata la
libreria MPI. Volendo utilizzare quest’ultima invece che scrivere un sottosistema ad-hoc, si pone il problema che, lanciando i processi, questi vengono messi
in esecuzione sulle macchine elencate nell’hostfile passato al comando mpirun
seguendo l’esatto ordine in cui gli host compaiono in questo file. Ciò ha l’effetto di sovraccaricare gli host elencati per primi e lasciare liberi gli ultimi, e
68
6. Conclusioni
questo ovviamente non è voluto. Pertanto, si rende necessario l’utilizzo di un
sistema che allochi in modo bilanciato i processi.
Thread L’ambiente di esecuzione distribuito che è stato implementato permette
una naturale estensione del linguaggio con il supporto ai thread. Questo potrebbe essere ottenuto introducendo ad esempio una parola riservata thread
che agisce da modificatore per le definizioni di funzioni. Prendiamo come
esempio la seguente definizione:
thread procedure t e s t t h r e a d ( )
begin
[...]
end ;
In questo caso, una chiamata a test thread provoca una chiamata remota, che
però viene eseguita in modo asincrono rispetto al resto del programma. In
altre parole, nello stub di inizializzazione di test thread non verrebbe emessa
l’istruzione WAIT. L’introduzione dei thread potenzialmente richiede un certo
sforzo supplementare: è necessario dotare il linguaggio dei consueti costrutti
di sincronizzazione, ma è anche necessario dotare le macchine virtuali di un
meccanismo di notifica di terminazione dei thread lanciati.
Bibliografia
[1] A.V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, tecniques and
tools. Addison-Wesley.
[2] Agostino Dovier and Roberto Giacobazzi.
Fondamenti dell’informatica:
Linguaggi formali, Calcolabilità e Complessità.
[3] Maurizio Gabbrielli e Simone Martini. Linguaggi di programmazione, Principi
e paradigmi. McGraw-Hill.
[4] Mary W. Hall, Brian R. Murphy, and Saman P. Amarasinghe. Interprocedural
parallelization analysis: A case study.
[5] Mary W. Hall, Brian R. Murphy, Saman P. Amarasinghe, Shih-Wei Liao, and
Monica S. Lam. Interprocedural analysis for parallelization.
[6] Steve Hoxey, Faraydon Karim, Bill Hay, and Hank Warren. The PowerPC
Compiler Writer’s Guide. IBM.
[7] Kenneth C. Louden. Compiler Construction - Principles and Pratice. PWS.
[8] Ronald Mak. Writing Compilers and Interpreters - An Applied Approach Using
C++. Wiley.
[9] Peter S. Pacheco. Parallel programming with MPI. Morgan Kaufmann.
[10] Andrew S. Tanenbaum. Architettura dei computer. UTET.
[11] Nicklaus Wirth. Compiler Construction.