Questo documento riassume i test eseguiti sul programma DFG per valutarne le prestazioni. I test sono stati eseguiti nel laboratorio LAB2 presso il Dipartimento di Elettronica, Informatica e Sistemistica dell'Università di Bologna. Si sono utilizzati i sistemi operativi:

• System V (SUNOS 5.5.1) con Java 1.1.4

• Windows NT4.0 con Java 1.2beta4

Si è anche creata una versione concentrata (chiamata Mand) che non utilizza una funzione nativa ma esegue tutti i calcoli in Java. 
 

• Test 1 - Confronto tra le prestazioni di DFG e di MandC.
• Test 2 - Confronto tra i tempi ottenuti con una funzione nativa e i tempi ottenuti con codice Java (confronto tra Mand e MandC).
• Test 3 - Considerazioni sulle prestazioni in presenza di guasti nel sistema.

Per effettuare questo test si sono utilizzate macchine il più possibile simili in prestazioni (sparcstation5 per il test effettuato sul sistema operativo Solaris e PentiumII 233Mhz per il test effettuato sul sistema operativo NT) e si è impostato ad un valore comune il parametro "carico di default". Inoltre, durante il test, sulle macchine non erano attivi altri programmi "pesanti" oltre a DFG. In questo modo si è cercato di eliminare possibili fattori esterni che potessero influenzare il risultato del test e quindi le valutazioni che da questo si possono ricavare. I valori riportati nelle tabelle sono la media di una serie di rilevazioni tutte effettuate nelle stesse condizioni.

Osservazioni:

Si è effettuato il calcolo di una serie di immagini diverse non solo nel loro costo (stimato), ma anche per le loro caratteristiche intrinseche, che ne determinano la reale complessità di calcolo. Ad esempio, le immagini 3 e 4 hanno lo stesso valore di costo, ma in realtà i punti dell'immagine 4 richiedono un numero di iterazioni mediamente molto superiore per essere calcolati (ved. Tabella 1). 
Tra queste caratteristiche è importante segnalare il grado di "simmetria" della complessità dell'immagine, che determina l'efficienza con cui il carico ad essa relativo viene ripartito tra gli slaves disponibili. Infatti, il tempo richiesto da un calcolo è dato dallo slave che impiega più tempo per calcolare la sua porzione di immagine. Per questo motivo, un'errata ripartizione del carico fa sì che molti slaves terminino il loro lavoro molto prima di altri, determinando così un drastico calo nelle prestazioni globali del sistema.

Questa considerazione mette in risalto il fatto che per un buon uso delle risorse è necessario impegnare in continuazione tutti gli slaves disponibili. Solo in questo modo è possibile ottenere prestazioni significativamente superiori a quelle ottenibili con un sistema concentrato. In altre parole, il programma DFG non è adatto a calcolare singole immagini, ma a svolgere il calcolo di un numero elevato di immagini contemporaneamente.

Esaminando i dati, si nota subito il fatto che DFG, quando c'è un solo slave a disposizione, è sempre più lento di MandC. Questo è ovviamente causato dall'overhead dovuto alla comunicazione tra le entità che costituiscono DFG.

All'aumentare del numero di slaves disponibili, il tempo di calcolo generalmente diminuisce. Questo però non accade sempre. Si consideri l'immagine 5: il tempo necessario per calcolarla è di soli 25.8sec con due slaves a disposizione, mentre è di 36.3sec con tre slaves. Questo è dovuto al fatto che questa immagine è fortemente asimmetrica per quanto riguarda la complessità di calcolo. La si può infatti suddividere in tre fasce orizzontali, delle quali quella centrale è estremamente più complessa da calcolare delle altre. 
Per questo motivo, quando si utilizzano tre slaves, due di questi terminano molto in fretta il proprio compito, mentre il rimanente impiega molto più tempo. Se invece si utilizzano due slaves l'utilizzo delle risorse è molto migliore (i due slaves terminano di calcolare quasi contemporaneamente).

Nota: E' possibile introdurre ottimizzazioni nella funzione di calcolo dell'insieme di Mandelbrot in modo da ridurre al minimo le disomogeneità alle quali si è accennato. La versione attuale di DFG non adotta alcun tipo di ottimizzazione. L'introduzione di questo tipo di ottimizzazione migliorerebbe notevolmente le prestazioni globali del sistema, sia perchè ridurrebbe il numero di iterazioni necessarie a riconoscere i punti appartenenti all'insieme di Mandelbrot, sia perchè permetterebbe una più equa ripartizione del carico tra gli slaves.

Un'altra osservazione importante che si può fare osservando i dati è che il sistema fornisce prestazioni migliori nel calcolo di immagini che hanno un costo molto elevato, perchè nel calcolo di tali immagini l'overhead introdotto dalla comunicazione costituisce una percentuale molto piccola del tempo di risposta totale. Infatti, il miglioramento ottenuto nel calcolo dell' immagine più costosa in assoluto passando da uno a cinque slaves è del 74.9% (immagine 4), mentre i miglioramenti ottenuti per le altre immagini vanno dal 47.2% al 58.3%.

Il grafico seguente riporta i dati della Tabella 1: 

Grafico 1

Di seguito sono riportati i tempi ottenuti sul sistema operativo Windows NT. In queste prove, il miglioramento delle prestazioni dovuto all'utilizzo di un numero di slaves maggiore è più marcato. Passando da uno a 4 slaves, il miglioramento va dal 54.9% (per l'immagine1, che essendo poco costosa risente maggiormente dell'overhead della comunicazione) al 76.3% (per le immagini 4 e 5, che sono le più costose e quindi risentono meno dell'overhead della comunicazione). 
 
 

Le caratteristiche delle immagini calcolate sono le seguenti:

IMMAGINE 1

Tipo Mandelbrot Larghezza 320 Altezza 240 Max Iter  800 x1 -0.1752 y1 1.04617 x2 -0.14204 y2 1.0213 Palette Palette1: burning Mandelbrot Costo stimato 61440000

IMMAGINE 2

Tipo Mandelbrot Larghezza 800 Altezza 600 Max Iter  400 x1 -0.7459947 y1 0.13231586 x2 -0.7417978 y2 0.12916816 Palette Palette1: burning Mandelbrot Costo stimato 192000000

IMMAGINE 3

Tipo Mandelbrot Larghezza 640 Altezza 480 Max Iter  1000 x1 -0.781408 y1 -0.1325861 x2 -0.7739277 y2 -0.138196 Palette Palette1: burning Mandelbrot Costo stimato 307200000

IMMAGINE 4

Tipo Mandelbrot Larghezza 640 Altezza 480 Max Iter  1000 x1 -0.7405319028 y1 -0.183407642 x2 -0.7405218018 y2 -0.183415426 Palette Palette1: burning Mandelbrot Costo stimato 307200000

IMMAGINE 5

Tipo Mandelbrot Larghezza 800 Altezza 600 Max Iter  1000 x1 -2.5 y1 1.5 x2 1.5 y2 -1.5 Palette Palette1: burning Mandelbrot Costo stimato 480000000

Questo test permette di confrontare i tempi ottenuti con una funzione nativa con quelli ottenuti con codice Java. Per effettuare questo confronto ci si è serviti di due applicazioni concentrate:

• Mand : utilizza una funzione scritta in Java per il calcolo delle immagini.
• MandC: utilizza una funzione nativa scritta in C per il calcolo delle immagini.

La Tabella 1 riporta i tempi ottenuti sulle workstation SUN: 
 

Tabella 1

L'incremento delle prestazioni dovuto all'uso di una funzione nativa è notevole. Nel caso dell'immagine 4, che è la più complessa da calcolare (nonostante il suo costo stimato non sia il più elevato), il tempo di generazione con MandC è un decimo di quello di Mand. Il grafico seguente riporta i dati della Tabella 1: 
 

Grafico 1

Di seguito sono riportati i dati relativi al test effettuato sul sistema operativo NT: 
 

Tabella 2

A differenza del caso precedente, l'uso di una funzione nativa peggiora le prestazioni del programma. Questo è dovuto al fatto che la versione di Java utilizzata (1.2beta4) supporta la compilazione JIT dei bytecodes e permette quindi di ottenere elevate prestazioni dal codice Java. Il grafico seguente riporta i dati della Tabella 2. 
 

Grafico 2

Parametri delle immagini utilizzate per questo test. 

Questo test permette di valutare il costo determinato dall'aver inserito nel sistema una forma di fault-tolerance che pemette di ottenere sempre un risultato anche in presenza di guasti agli host DFGSlave. In particolare, lo scopo di questo test è fornire una misura dell'overhead dovuto ad una ridistribuzione di carico seguita alla caduta di uno o più slaves.

Osservazione: se uno slave cade durante il calcolo, il lavoro che aveva svolto fino al momento del guasto viene perso e deve essere ripetuto dagli altri slaves. Visto che ciò che interessa è misurare l'overhead introdotto da una ridistribuzione di carico, è necessario mantenere distinto questo valore dal tempo "perso" dallo slave guasto a calcolare una porzione di immagine che alla fine non viene utilizzata e deve essere ricalcolata.

Si è quindi pensato di eseguire il test inserendo nella Tabella mantenuta da DFGServer un numero di slaves superiore a quello realmente disponibile. In questo modo, all'atto di una nuova richiesta, DFGServer è stato costretto ad effettuare immediatamente una o più ridistribuzioni di carico. La descrizione dei passi eseguiti per effettuare il test è riportata di seguito:

• avvio di DFGServer, di tre DFGSlave e di un DFGClient
• interruzione di un DFGSlave: visto che lo slave interrotto era inattivo al momento del guasto, DFGServer non si accorge della sua caduta.
• invio di una richiesta e misura del tempo di completamento (VALORE A): DFGServer non riesce a contattare lo slave appena interrotto ed esegue una ripartizione di carico tra gli altri due slaves.
• ripristino del DFGSlave interrotto e sua nuova interruzione (per reinserirlo nuovamente in Tabella).
• interruzione di un altro DFGSlave: a questo punto sono presenti tre slaves in Tabella, ma in realtà uno solo è attivo.
• invio di una richiesta e misura del tempo di completamento (VALORE B): il risultato ottenuto comprende tre ridistribuzioni di carico.

Tabella 1

L'overhead introdotto è abbastanza modesto. Si consideri però il fatto che il test è stato effettuato senza che fossero in corso altri calcoli, vale a dire nelle condizioni più favorevoli possibili.

Osservazione: In una situazione senza guasti, ogni slave utilizza un solo thread per svolgere il calcolo che gli è stato assegnato e al termine del calcolo spedisce il risultato corrispondente a DFGServer. Il tempo di servizio di uno slave è quindi dato dalla somma tra il tempo di calcolo e il tempo di trasmissione del risultatato (che nei nostri test non è mai stato preso in considerazione perchè è molto piccolo rispetto al tempo di calcolo). Nel caso di una ridistribuzione di carico, invece, ogni slave rimasto attivo si trova a calcolare più di una porzione dell'immagine richiesta, e lo fa utilizzando thread distinti. Al termine del calcolo di ciascuna porzione, la spedisce a DFGServer. Durante questa spedizione, però, il calcolo relativo alle altre porzioni dell'immagine continuano e quindi il tempo di trasmissione del risultato è in definitiva limitato all'ultima porzione di immagine trasmessa a DFGServer. In questo senso, si può dire che l'overhead di una ridistribuzione sia parzialmente compensato da una maggiore efficienza nella restituzione del risultato.

Il test è stato eseguito in LAB2 sulle macchine lia (si sono utilizzate quattro sparcstation5, tutte inizializzate ad uno stesso valore di carico e sulle quali era attivo solamente il programma DFG) , cercando di eliminare possibili fattori esterni che potessero influenzare i risultati del test. Il test è stato ripetuto varie volte e i valori riportati nella tabella sono valori medi.

L'insieme di Mandelbrot è l'insieme dei punti C del piano complesso per i quali non è divergente la serie definita dalla legge ricorsiva 

Iterando la formula per ogni punto del piano complesso, è quindi possibile suddividere i punti in due categorie:

• punti che appartengono all'insieme di Mandelbrot
• punti che non appartengono all'insieme di Mandelbrot

• se l'orbita va all'infinito significa che la serie diverge e quindi C non appartiene all'insieme.
• se l'orbita non va all'infinito significa che la serie non diverge e quindi che C appartiene all'insieme.

E' anche possibile assegnare un colore ai punti che non appartengono all'insieme di Mandelbrot. Esistono molti modi per farlo: il più semplice è detto "metodo del tempo di fuga" e consiste nell'assegnare ai punti un colore che dipende dal numero di iterazioni che sono necessarie per capire che non appartengono all'insieme.

Si può dare una spiegazione intuitiva del nome di questo metodo: si immagini che tutti i punti del piano siano attratti sia dall'insieme di Mandelbrot che dalla retta impropria. E' quindi facile capire perchè i punti più vicini all'insieme abbiano orbite che sfuggono all'infinito più lentamente di quelle relative a punti più lontani dall'insieme. 
In quest'ottica, il colore dei punti può essere interpretato come il tempo impiegato dalla loro orbita per sfuggire all'attrazione dell'insieme di Mandelbrot e corrisponde ad una stima della velocità con cui l'orbita diverge. 

La funzione nativa utilizzata nel programma DFG ha il compito di assegnare un colore ad ogni punto di un'area rettangolare del piano complesso (rappresentata da un array di interi).

Per quanto appena detto, le operazioni svolte dalla funzione per ogni punto C dell'immagine sono le seguenti:

• Iterazione della formula Z_n = Z_n-1²+ C partendo dal valore iniziale Z₀=  0.
• Se il modulo di Z_n diventa maggiore di 2, allora C non appartiene all'insieme. Il colore da assegnargli dipende dal numero di iterazioni effettuate (n). Dato il valore n, la funzione ottiene i valori RGB del colore da assegnare al punto richiamando un metodo di una sottoclasse della classe Palette.
• Se dopo N_MAX iterazioni il modulo di Z_n non è ancora diventato maggiore di 2, allora si assume che C appartenga all'insieme e lo si colora di nero.

Esempi:
Vediamo come assegnare un colore ad un punto. Iniziamo col considerare un punto al di fuori dell'insieme di Mandelbrot: 
C = -0.5 + i.
L'iterazione della formula Z_n = Z_n-1² + C produce i seguenti valori di Z_n: (l'immagine mostra i punti corrispondenti sul piano complesso). 
 

Passo # Valore_Corrente Distanza  dall'origine  1 -0.5 + i  1.12 2 -1.25  1.25 3 1.06 + i  1.46 4 -0.37 + i * 3.1 3.15

Alla terza iterazione, il modulo di Z_n diventa maggiore di 2. Questo significa che C non appartiene all'insieme di Mandelbrot. Dato che il numero di iterazioni che sono state necessarie per determinarlo è 3, al punto C viene assegnato il colore n.3 della palette.

Ripetiamo il procedimento con un punto appartenente all'insieme di Mandelbrot: C = 0.2 + i * 0.5. In questo caso, il modulo di Z_n non diventerà mai maggiore di 2 per nessun valore di n. Quando viene raggiunto il numero massimo di iterazioni, si assume che C appartenga all'insieme di Mandelbrot e lo si colora di nero. 
 

Passo # Valore_Corrente Distanza  dall'origine 1 0.2 + i * 0.5 0.54  2 -0.01 + i * 0.7 0.7  3 -0.29 + i * 0.49 0.57  4 0.05 + i * 0.22 0.22  5 0.15 + i * 0.52 0.54 6 -0.05 + i * 0.66 0.66  7 -0.23 + i * 0.44 0.48  8 0.06 + i * 0.3 0.3  . . . . . . . . . . . . . .  . . . .

Per maggiori informazioni sull'insieme di Mandelbrot: Fractal Explorer

    L'applicazione realizzata, un generatore di frattali, è solo delle possibili applicazioni del sistema progettato, che è facilmente estendibile per trattare problemi di diversa natura nell'ambito del web computing.

    E' infatti molto semplice introdurre nuovi tipi di Messaggio ed estendere le capacità di DFGServer e dei DFGSlave (introducendo nuove classi Gestori). E' anche semplice modificare le politiche di ripartizione del carico, che sono interamente specificate in un metodo della classe Tabella. L'unica limitazione è costituita del fatto che non è prevista alcuna interazione tra i DFGSlave, quindi il sistema è adatto a svolgere calcoli che possano essere decomposti in parti autonome.

    E' anche possibile implementare semantiche diverse da quella adottata, ad esempio spedendo richieste uguali a vari slaves e attendendo la risposta dello slave più veloce a terminare (o della maggioranza, o di tutti con confronto delle risposte). 
 

POSSIBILI MIGLIORAMENTI:

• Introdurre la possibilità di scelta fra l'uso di una funzione nativa e una funzione Java per il calcolo. Come osservato nella sezione dedicata all'analisi delle prestazioni, infatti, l'uso di una funzione nativa è opportuno solo se la JVM utilizzata non supporta la compilazione JIT dei bytecodes.
• Riduzione dell'occupazione di memoria delle immagini modificandone il formato come descritto nella sezione dedicata al calcolo. I test eseguiti sul sistema sono stati effettuati nell'ambito di una rete locale (Ethernet) e quindi le elevate dimensioni delle immagini non hanno influito in modo apprezzabile sui tempi di risposta misurati.
• Riduzione delle dimensioni dei messaggi di controllo scambiati nel sistema, sostituendo il loro campo "Type" (che attualmente è una stringa), ad esempio, con un singolo carattere; nella versione attuale si è scelto di utilizzare una stringa per una maggiore leggibilità del codice e perchè le dimensioni dei messaggi di controllo sono molto piccole rispetto alle quantità di dati scambiate per il trasferimento delle immagini.
• Ottimizzazione della funzione di calcolo con algoritmi opportuni.
• Introduzione di un time-out che tenga conto della possibilità che il carico di uno slave possa variare sensibilmente durante il calcolo e di conseguenza della possibilità da parte di DFGServer di effettuare autonomamente ridistribuzioni di carico.
• Produzione della documentazione.
• Introduzione modalità "--silent" e "--verbose" in DFGServer e DFGSlave.
• Miglioramento dell'interfaccia utente, (in particolare la possibilità di utilizzare il mouse per selezionare un'area da ingrandire sulle immagini generate).