An XML-based virtual machine for distributed
computing in a Fork/Join framework
Giuseppe Cutuli, Enzo Mumolo, Marco Tessarotto
DEEI, Universita’ di Trieste, Italy
Dipartimento di Elettrotecnica, Elettronica ,
Robotics
Informatica, Universita' di Trieste
Speech, Multimedia and
Technologies Lab
http://smartlab.univ.trieste.it
1/39
Introduction
 “GRID Computing”: a High Performance Computing
paradigm based on sharing computing resources in internet
 Complex problems in theoretical physics, medicine,
genetics, astronomy, financial, whether analysis …
 Some requirement of GRID:
- multi-platform nodes  Java Virtual Machine
- dynamic environment: hardware and software moving
 A typical GRID monolytic architecture:
Byte code + data
p2p node
p2p node
Dynamic linking
Security
results
Verification 2
Optimization
2/39
Introduction (cont.)
 some problems of the monolythic architecture:
performance – security - scalability
 The point of view used in this work:
XML Interpretation
Algorithm described in XML + data
p2p node
p2p node
results
 Why using XML to describe algorithms in GRID?
- efficient algorithms distribution (HTTP’s Post )
- efficient XML interpretation
3
Motivations of this work
• To increase computing power on a mobile robot
• Image – demining applications
• Distributed environment
Radio LAN
LAN
4
8/39
Il Meta-linguaggio XML
 L’XML (eXtensible Markup Language) è un linguaggio di
meta – markup, specifica una sintassi per altri linguaggi di
markup semantici
<?xml version="1.0"?>
 Struttura
<!DOCTYPE nome descrittivo del documento [
<!ELEMENT elemento 1 (second1.1, ..,>
 Logica:
 Prologo
 Elemento Document o
Document Type Definition (DTD)
<!ELEMENT second1.1 tipo>
 Fisica:
 Contenuti e Funzionalità
Attributo1
 Sintassi
 Documenti validi e ben formati
….
….
<!ELEMENT elemento N>
<!ATTLIST elementoN
tipo
Valore
….
]>
<!ENTITY nome
“definizione”>
….
<elemento 1>Contenuti e funzionalità
….
</elemento 1>
5
9/39
XML-RPC: chiamata a procedure remote
 Header HTTP per i parametri di comunicazione
 Corpo XML per passare la richiesta coi parametri d’esecuzione
Richiesta
Risposta
URI al codice di gestione richieste HTTP
User-Agent
Host
Content-Type
Content-length
<?xml version="1.0"?>
<methodCall>
<methodName>
nome procedura richiamata
</methodName>
<params>
<param>
Parametro 1
</param>
….
</params>
</methodCall>
Verifica Trasmissione
Chiusura connessione
Content-Type
Content-lengthDate
GMTServer: agente di collegamento del server
<?xml version="1.0"?>
<methodResponse>
<methodResponse>
<params>
<fault>
parametri di ritorno
<value>
</params>
struttura che segnala
</methodResponse>
l’errore
</value>
</fault>
</methodResponse>
6
10/39
XML-RPC: chiamata a procedure remote
 Schema che descrive una comunicazione RPC
7
12/39
Architettura del sistema

Esempio
direstituzione
rete
to
-risultati
peer
 Chiamata
 Chiamata
tra
Schema
i Nodi
tra Peer
con
i Nodi
–Peer
to Peer
– peer
– to– –
dei
(nostra
peer
(teorico)
realizzazione)
8
13/39
Architettura software
 Non esiste una precompilazione del documento sorgente
 Il documento viene analizzato (Parsing)  eventi
 Eventi  interprete scritto in Java (esecuzione)
Lettura
Parsing
*** ** *** **
•* ** * *** *
•** * **
•*** ** * **
•** * ** **
•** * ** ** **
•* **********
*** ** *** **
•* ** * *** *
•** * **
•*** ** * **
•** * ** **
•** * ** ** **
•* **********
Esecuzione
*** ** *** **
•* ** * *** *
•** * **
•*** ** * **
•** * ** **
•** * ** ** **
•* **********
Interprete
Scritto in Java
9
14/39
Il Meta-linguaggio XML-VM
 Permette di descrivere un algoritmo con XML
 I Tag XML diventano le istruzioni del nuovo linguaggio
 Il linguaggio si può vedere come un tipo semplificato di
Assembler
 Si è deciso di non sviluppare una DTD del linguaggio per
non appesantire la fase d’interpretazione
 Il controllo della sintassi è affidato allo stesso compilatore
Java
10
15/39
Il Meta-linguaggio XML-VM (continua)
Caratteristiche principali del linguaggio:
 Attributi come parametri
 Strutture dati
 Registro
 Disco Virtuale
 I dati sono immagazzinati nel Disco Virtuale
 I dati possono essere elaborati solo nel Registro
 Abbiamo introdotto il tipo di dato Index
11
16/39
Le istruzioni Matematiche
Istruzioni:
Esempio
<OPER target=“0” op1=“13” op2=“11”
 ADD
<ADD target=“2”
first=“3” second=“9”/>
op3=“9” command=“*+”/>
 CONV
 DIV
 ELEV
 MUL
 OPER
 SUB
Registro
r0
r1
r2
r3
r4
r5
30 1 m9 m3
r8
r9
6
r10
r11
2
r6
r7
r2
r12
r13
r14
r15
12
12
17/39
Le istruzioni di Spostamento Dati
Esempio
<LOAD
<STORE
<LOADregpointed=“4”
register=“4”
topointed=“5”
index=“10”/>
index=“3”/>
from=“4”/>
Istruzioni:
 LOAD
Registro
r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15
 MOVE
r5 m3
 STORE
Disco Virtuale
m0 m1 m2 m3 m4 m5 m6 m7 m8 m9 m10m11m12m13m14
1
m3
r5
7
12
r5
m15 m16 m17 m18 m19 m20 m21 m22 m23 m24 m25 m26 m27 m28
13
m29
18/39
Le istruzioni Logiche
Esempio
Istruzioni:
 CMP
 JEQ
 JGR
 JNEQ
 JNGR
 LABEL
 QUIT
 START
 STRUCT
<CMP
<CMPfirst=“6”
first=“6” second=“11”/>
second=“9”/>
Flag
Flag==“ “3
2 ””
Registro
r0
r1
r2
1
r8
r9
6
r3
r4
r5
m3
r10
r11
2
r6
r7
2
r12
r13
r14
r15
12
14
19/39
Le istruzioni di Chiamata
Esempio
Istruzioni:
 CALL
<FORK id=“N00” file=“pippo.xml” name=“via”
<JOIN to=“m15-m19”/>
to=“m15-m19” clone=“m5-m9”/>
Registro
r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15
 FORK
 JOIN
 LOCALCALL
 RETURN
Disco Virtuale
m0 m1 m2 m3 m4 m5 m6 m7 m8 m9 m10m11m12m13m14
1
m3
7 8 12 5 15 r5
m15 m16 m17 m18 m19 m20 m21 m22 m23 m24 m25 m26 m27 m28
*RESERVED*
5 7 8 12 15
15
m29
20/39
Fork/Join
 L’istruzione Fork è simile ad una chiamata a procedura
classica, solo che lancia due processi in parallelo
 Il compito di raccordo è svolto dall’istruzione Join, che
sincronizza i flussi di programma separati col Fork
P
F
join
B
16
21/39
Fork/Join
Esistono diverse sintassi per descrivere il Fork/Join
 Si può usare un contatore delle chiamate Fork
 Si possono associare le istruzioni a delle variabili
17
22/39
Fork/Join
Esempio di chiamata Fork/Join in XML-VM
……
<FORK id=“N00” file=“pippo.xml” name=“via” to=“m3-m5” clone=“m7-m9”/>
……
……
*** ** *** ** ** * **
……
<LABEL name=“via”/>
** * ** ** * **
……
•*** ** * ** ** *
•* ************
……
•** * ** ** **
•* ************
……
•** * ** ** **
•* ************
……
<RETURN from=“r6-r8”/>
……
<JOIN to=“m3-m5”/>
……
……
……
……
<QUIT/>
18
23/39
Le istruzioni Varie
Esempio
Istruzioni:
 RANDOM
<RANDOM to=“m15-m25” type=“int” mul=“10”/>
Registro
r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15
 SHOW
Disco Virtuale
m0 m1 m2 m3 m4 m5 m6 m7 m8 m9 m10m11m12m13m14
1
m3
7
12
r5
m15 m16 m17 m18 m19 m20 m21 m22 m23 m24 m25 m26 m27 m28
8 3 2 3 5 9 0 6 1 7 2
m29
24/39
Il Parser Java
 È un traduttore in grado d’interpretare un documento XML
 Permette al linguaggio Java di trattare le informazioni
contenute nel documento come eventi concatenati
 Esistono due tipi di specifiche per il Parser
 Sax 1.0 (contenuto dei Tag ed attributi)
 Sax 2.0 (anche analisi DTD, fogli di stile ed altro…)
 Prima realizzazione: Xerces dell’Apache (Sax 2.0)
 Realizzazione definitiva: MinML (Sax 1.0)
20
25/39
L’interprete di XML-VM
 È scritto in Java per potersi adattare ad ogni piattaforma
 È strutturato nei seguenti 14 file
 File che implementano la Macchina Virtuale
 Index.java
 xmlvmcontenthandler.java
 xmlvm.java
 xmlvmgeneric.java
 xmlvmcontext.java
 xmlvmStack.java
 XmlvmException.java
 File che contengono procedure main()
 saxtest.java
 xmlvmCall.java
 xmlvmnamres.java
 File con compiti vari
 Methods.java
 PseudXmlRpc.java
 xmlvmMachine.java
 xmlvmMachineTable.java
21
26/39
L’interprete di XML-VM (continua)
public Object startExecution(Object[] arg, xmlvmMachine Machine) throws Exception{
Inizializzazioni;
Scansione rapida del documento per la ricerca dei Tag Label;
Verifica che l’intestazione del documento sia corretta;
Cerca nel documento il Tag <START/> o quello <STRUCT/>, e inizializza la variabile i con
la posizione del Tag appena trovato;
try {
FOR(i < tag.getChildrenCount(); i++) {
SE (il Tag[i] è uno tra ADD LOAD MOV STORE SUB …) Allora
lancia la procedura associata;
Altrimenti {
Per START e LABEL non fare niente;
Per STRUCT ripristina le informazioni presenti nell’array Arg[];
Per JEQ, JNEQ, JGR, JNGR lancia le procedure associate ed aggiorna i;
Per RETURN esegui la procedura Return(tag);
Per SHOW mostra il contenuto del registro indicato;
Per QUIT esci dal ciclo;
}
}
} catch(Exception e)
SE (non termina con QUIT) Lancia un errore e scrivi “non termina con Quit”;
}
22
27/39
L’interprete di XML-VM (continua)


xmlvmnamres
Saxtest.java
xmlvmCall
class nameres implements XmlRpcHandler {
Inizializzo la xmlvmMachineTable, inserendo tutti i Nodi a disposizione:
nameres() {
public
{ implements XmlRpcHandler {
public class
class
} saxtest
xmlvmCall
public class xmlvmnamres {
public
main(String[]
arg) [])
throws
Exception
public
publicstatic
Object
staticvoid
void
execute
main(String
(String method,
args
throws
Vector
Exception
v) throws{ Exception
{
{
WebServer webserver = new WebServer (10000); //attivo il Server XML-RPC
Definisci
l’oggetto
“xmlvmMachine”
connameres());
l’ip e la porta del risolutore dei nomi, e
Vector
vResult =
Methods.execute(method,v);
webserver.addHandler
("$default", new
chiamalo
“table”;
}
return
(vResult);
xmlvmcontext
ct = new xmlvmcontext();
} }
ct.init();
public Object execute (String method, Vector v) throws Exception {
Object[]
new main(String
Object[2]; args []) throws Exception {
publicargs
static= void
args[0]
= "http://...
... .xml"; è=per
//nome
del
documento
XML-VM dadel
elaborare
Riconosci
WebServer
che la webserver
chiamata
new
una
WebServer
vera
a propria
(...porta...);
risoluzione
nome;
ct.parseXmlvmDoc(args[0].toString());
//Esegui
del documento
Confronta
webserver.addHandler
l’identificativo che("$default",
ti è stato passato
new
xmlvmCall());
conil Parsing
quelli disponibili;
Object
o = ct.startExecution(args,
table); i //Lancia
l’esecuzione
del
Se} l’identificativo
è “N00”, allora restituisci
dati di uno
dei Nodi disponibili
a caso;
}}Altrimenti restituisci quello specificato;
}
}
}
}
23
28/39
L’interprete di XML-VM (continua)
Sistema distribuito completo
24
29/39
L’interprete di XML-VM (continua)
Esempio
Esempio
Esempio
Esempio
d’istruzione
di codice
d’istruzione
d’istruzione
d’istruzione
perper
Spostamento
leLogica
Chiamate
Matematica
dati
public void LocalCall(xmlvm tag) throws Exception {
public
void
Store(xmlvm
tag)
throws
Exception
public
void
Div(xmlvm
tag)
throws
Exception
{ {{
public
void
Cmp(xmlvm
tag)
throws
Exception
Estrai gli
attributi
TO, NAME;
Aggiungi
un elemento
all’XML-VMStack,
dove sono memorizzati il registro al momento
Estrai
gli
attributi
TO,
TYPE,
FROM
e TOPOINTED;
Estrai
RESULT,
REST,
FIRST
e SECOND;
Estraigli
gliattributi
attributi
FIRST
e
SECOND;
della
chiamata ed
i parametri
inviati;
Se
(FROM.compareTo(“”)
!=sono
0),
carica
il valore
dellaa cella
R[FROM];
Se
R[FIRST]
e R[SECOND]
numeri,
allora
Se
(FIRST>SECOND),
aggiorna
la
variabile
diinflag
1;parametri
Metti
nelle
celle
del
disco
virtuale
dalla
1
poi
i
altrimenti
il valore contenuto
all’interno
del TAG; di flag a 2; annidati nell’ordine in cui
Se
(RESULT.compareTo(“”)
== 0),laallora
Altrimenti cairca
Se
(FIRST<SECOND),
aggiorna
variabile
appaiono;metti
Se (TO.compareTo(“”)
!= 0),
metti
valore
caricato in
il risultato
della divisione
in DV[TO];
R[FIRST]
Altrimenti
Seil (FIRST==SECOND),
aggiorna la variabile di flag a 3;
Salta
all’etichetta
definita
dal
nome
NAME;
altrimenti mettilo nellarispettando
locazione ilditipo
memoria
virtuale puntato da R[TOPOINTED];
di datodel
deldisco
risultato;
Raccogli i Altrimenti
risultati della
chiamata;
mettilo
in R[RESULT];
}Memorizza nelle celle di memoria
dall’attributo TO;
}
Se (REST.compareTo(“”)indicate
!= 0), allora
metti il resto della divisione in R[REST];
}
}
25
30/39
L’interprete di XML-VM (continua)
Pseudo-codice istruzione Fork
Join
public void Fork(xmlvm tag) throws Exception {
Estrai gli attributi TO, IP, FILE, NAME e CLONE;
public
tag)
throws Exception
Effettuavoid
una Join(xmlvm
chiamata RPC
al risolutore
dei nomi e{ aggiorna l’IP;
Prepara nel vettore args tutti i parametri necessari per l’invio della richiesta remota,
ovverogli
Estrai
il registro
attributi per
TO e
intero
TOPOINTED;
e la sezione del disco virtuale indicata dall’attributo CLONE;
Inizializza le celle del disco
SE(TO.compareTo(“”)
!= 0) virtuale descritte da “TO” al valore “*RESERVED*”;
ForkThread
verifica che
remoteCall
le celle individuate
= new ForkThread();
dall’attributo TO non siano ancora *RESERVED*;
RemoteCall.start();
se sono ancora *RESERVED*, esegui un ciclo che continui a monitorare le celle;
Altrimenti
}
{
protected
class
ForkThread
{ puntata dalla prima parte dell’attributo
verifica che
le celle
contigueextends
a partireThread
dalla cella
Definizione
delleper
Variabili
locali;
TOPOINTED
una lunghezza
pari alla seconda parte dello stesso attributo non siano
public
ancora
void*RESERVED*;
run() {
se sonoEffettua
ancora *RESERVED*,
esegui
un ciclo che
continui
a monitorare
le celle; all’IP;
la richiesta remota
direttamente
verso
la macchina
corrispondente
}
Digli di eseguire il documento XML-VM indicato nell’attributo FILE a partire dalla
procedura etichettata col nome NAME;
}
Raccogli i risultati della chiamata;
Memorizza nelle celle di memoria indicate dall’attributo TO;
}
26
}
31/39
Accorgimenti presi per gli esperimenti
 Risolutore dei nomi per raccogliere le misurazioni
 Procedure di rilevazione dei tempi
 Procedure di rilevazione del flusso di dati XML-RPC
 Strumenti a disposizione per gli esperimenti
 16 computer eterogenei
 8 Pentium III 800MHz, Windows2000, 128 MB RAM
 8 Celeron 400MHz, WindowsNT 4.0, 64 MB RAM
 Impostazioni adottate negli esperimenti
 Nodo centrale escluso dalla computazione (Pentium III)
 Misurazioni in funzione del numero di macchine coinvolte
 Carico doppio sui Pentium III
 I Pentium III sono le prime macchine introdotte
27
32/39
Risultati Sperimentali
 Tre tipi di esperimenti
 Una Sommatoria
 Un Integrale
 Un Ordinamento Quick Sort
13
( 2 i 1)
(
2
i

1
)
x
dx
 i 1
5
12
f(x)
x
28
33/39
Esempio di sorgente XML-VM
Codice XML-VM per la Sommatoria
<?xml version='1.0'?>
<XMLVM>
<START/>
<STORE to="12" type="int">
1
</STORE>
<STORE to="0" type="index">
m1
</STORE>
<STORE to="13" type="int">
0
</STORE>
<STORE to="14" type="int">
2
</STORE>
<STORE to="15" type="index">
m0
</STORE>
<STORE to="16" type="int">
20
</STORE>
<LOAD register="15" index="15"/>
<LOAD register="16" index="16"/>
<ADD first="15" second="16"/>
<STORE to="15" from="15"/>
<LOAD register="29" index="14"/>
<LOAD register="30" index="13"/>
<JGR to="For1"/>
<LOAD register="31" index="12"/>
<LABEL name="EndFor1"/>
<MOVE target="15" source="30"/>
<STORE to="17" type="index">
<STORE to="10" type="int">
m0
4000000
</STORE>
</STORE>
<LOAD register="17" index="17"/>
<STORE to="11" type="int">
<LOAD register="16" index="16"/>
100000
<ADD first="17" second="16"/>
</STORE>
<LOAD register="0" index="10"/>
<STORE to="17" from="17"/>
<MOVE target="17" source="30"/>
<LOAD register="1" index="11"/>
<STORE to="9" from="2"/>
<DIV result="2" first="0" second="1"/>
<JOIN topointed="m17[m9]"/>
<CONV register="2" to="int"/>
<MOVE target="3" source="30"/>
<MOVE target="3" source="30"/>
<LABEL name="For1"/>
<LOAD register="6" index="13"/>
<CMP first="2" second="3"/>
<LOAD register="8" index="17"/>
<LABEL name="For2"/>
<JNGR to="EndFor1"/>
<CMP first="2" second="3"/>
<MUL target="4" first="3" second="1"/>
<JNGR to="EndFor2"/>
<ADD target="5" first="4" second="1"/>
<LOAD register="7" pointer="8"/>
<STORE to="1" from="4"/>
<STORE to="2" from="5"/>
<ADD first="8" second="31"/>
<FORK
id="N00"
file="http://10.0.0.3:80/SommaNodo_xmlvm.xml"
name="Somma" to="m15[m12]" clone="m0[m14]"/>
<ADD first="3" second="31"/>
<LOAD register="15" index="15"/>
<ADD first="6" second="7"/>
<JGR to="For2"/>
<ADD first="15" second="31"/>
<LABEL name="EndFor2"/>
<STORE to="15" from="15"/>
<QUIT/>
<ADD first="3" second="31"/>
</XMLVM>
<MOVE target="15" source="30"/>
29
34/39
Risultati Sperimentali (Sommatoria)
Grafico dei
Grafico
Tempidegli
per numero
Speedups
di macchine
16
14
350
300
12
10
Tempi, sec
Speedups
250
Ideale
200
8
6
4
2
Somma
150
Celeron ideale
100
50
0
0
1
2 1 3 2 4 35
46
5
7
86
97 108 11 912 10
13 11
14 12
15
13
14
15
di macchine
Num ero Numero
di m acchine
30
35/39
Risultati Sperimentali (Integrale)
Grafico
Grafico
Grafico
dei
dei
Grafico
stimato
Tempi
Tempidegli
per
per
perPentium
numero
Speedups
Pentiumdi
eeCeleron
macchine
Celeron
1200600
1200
16
141000
500
1000
400
800
800
Tempi, sec
Tempi, sec
10
Pentium IIIIdeale
e Celeron
Integrale
Pentium III
Celeron teorico
300
600
8 600
11
3
2
4
3
2
5
4
6
35
7
6 4 7
8
9
85 9
10
11
10
6
15
2
13
1
00
11
0
9
0
7
2
100
200
200
5
4
Celeron
Ideale
Celeron
200
400
400
3
6
1
Speedups
Tempi,
sec
12
12
Num
ero
di m acchine
Num ero
di m
acchine
Numero
Numdi
eromacchine
di m acchine
11
13
12
7
14
13
14
15
15
31
36/39
Risultati Sperimentali (Quick Sort)
Grafico
Grafico
Volume
degli
dei
Grafico
Tempi
dati
Speedups
trasferiti
degli
per numero
Speedups
riscalato
via XML-RPC
di macchine
(Pentium)
Volume di dati trasferito
16
8 50
510
Tempi, sec
Speedups
Speedups
612
45
40
35
30
48 25
36 20
24 15
12 10
00
100%
Numero caratteri
714
80%
60%
Quick Sort
QuickSort riscalato
40%
Celeron ideale
20%
0%
5
0
Ideale Pentium III
Ideale Pentum III
QuickSort
Caratteri inviati in
totale
11 21 322 4 3 5 3 46
Integrale
Media Caratteri per
chiamata
1687313
45603
4 8 9 510 11 612 13 714 15
7
5110525
6
7
8
9 10
11 12
1416
13
14
15
di
macchine
Num ero
di
m acchine
Numero
di macchine
37189
930
Somma Numero
32
37/39
Risultati Sperimentali (Parsing)
 Il Tempo di Parsing comprende il download e l’analisi del
documento XML
 Si effettua il Parsing dei documenti XML-VM ad ogni
chiamata remota
Tabella dei tempi di Parsing
T
e
m
p
o
m
e
d
i
o
d
i
P
a
r
s
i
n
gT
e
m
p
o
m
e
d
i
o
d
i
e
s
e
c
u
z
i
o
n
eP
e
r
c
e
n
t
u
a
l
e
S
o
m
m
a
:
3
8
,
3
9
4
3
9
0
2
4
7
8
1
4
3
,
2
6
7
9
3
0
,
0
4
9
1
%
I
n
t
e
g
r
a
l
e
:
5
3
,
0
9
1
4
5
2
9
9
1
0
6
6
2
8
,
0
9
2
3
0
,
0
4
9
8
%
Q
u
i
c
k
S
o
r
t
:
5
1
,
8
1
4
0
3
5
0
9
9
7
2
7
,
2
7
7
1
9
3
0
,
5
3
2
7
%
33
38/39
Conclusioni
Metodi variabili:
 Trasferimento dei metodi in Java
Nodo
Sorgente
Java
Nodo Remoto
• Compilazione
• Esecuzione
 Trasferimento dei metodi con XML-VM
Nodo
Sorgente
XML
Nodo Remoto
• Parsing
• Esecuzione
 Nel Nodo remoto ci sono:
 Parser MinML
 Codice eseguibile (~100KB)
34
39/39
Conclusioni
 Si è progettato e sviluppato un sistema per Grid Computing
 Si è utilizzato XML per descrivere algoritmi
 Si è utilizzato Java per implementare la macchina virtuale
 I risultati raccolti hanno risposto adeguatamente alle attese
 I grafici delle prestazioni dimostrano efficienza di calcolo
 I Tempi di download e d’analisi dei metodi sono leggerissimi
 Non è stato affrontato il problema della distribuzione del
Carico e della tolleranza ai guasti
 Non sono stati affrontati i problemi di sicurezza e
programmazione complessa
35