PRESENTAZIONE | SPECIFICHE | BILANCIAMENTO DEL CARICO | TOLLERANZA AI GUASTI| ANALISI DELLE PRESTAZIONI | METODO DI CALCOLO | CONCLUSIONI


Problemi di bilanciamento del carico:
Come già sottolineato, DFGServer deve mantenere una struttura dati (chiamata Tabella) in cui memorizzare gli slaves attualmente disponibili, la loro collocazione (nome dell'host e numero di porta) e il loro carico attuale. Un esempio di tale struttura dati è il seguente:

Tab.1

nome host
numero porta
carico
lia09
20000
176800000
lia07
20001
176800000
lia06
20001
100000000

Nota: l'implementazione parallela degli slaves rende inutile l'esecuzione di più di una istanza di DFGSlave per ogni host e permette di identificare ogni DFGSlave con l'host su cui opera. Nel sistema realizzato, comunque, viene utilizzata la coppia nomehost : numeroporta per individuare uno slave.

Definizione del  parametro "carico":
Per poter quantificare il carico a cui è sottoposto uno slave si deve innanzitutto definire una regola per assegnare ad ogni richiesta di servizio un numero intero che ne rappresenti il costo, vale a dire una stima delle risorse di calcolo necessarie per servire la richiesta. Questo valore deve tenere conto dei seguenti parametri:

Una stima del costo di una richiesta di servizio in cui l'immagine da calcolare sia di 640x480 pixel con un numero massimo di iterazioni pari a 500 è data da 640*480*500 = 153,6E6. Questa stima è molto inaccurata perchè presuppone il fatto che ogni pixel dell'immagine per essere calcolato richieda un numero di iterazioni pari al numero massimo di iterazioni. D'altra parte, questa stima fornisce un valore che permette di confrontare due richieste diverse con un grado di approssimazione che è ritenuto accettabile.

Il parametro "carico" è definito come la somma del costo delle richieste servite da un determinato slave in un certo istante. Al numero ottenuto viene anche sommato un valore di default comunicato dallo slave all'atto della sua registrazione nella Tabella. Quest'ultimo valore deve essere specificato manualmente all'atto della esecuzione dello slave e serve a tenere conto del tipo di macchina su cui lo slave sta eseguendo e delle risorse che sono disponibili su di essa. Non è previsto che questo "handicap" possa essere modificato durante l'esecuzione dello slave. La scelta di questo valore (peraltro opzionale) deve essere effettuata sulla base della conoscenza delle macchine su cui verranno eseguiti gli slaves.

Esempio (ved. tab.1):
lia06, lia07 e lia09 hanno tutti un carico di default pari a 100E6. lia06 non sta calcolando, mentre lia07 e lia09 stanno calcolando (metà ciascuno) un'immagine di 640x480 pixel con un numero massimo di iterazioni pari a 500.


Algoritmo per la suddivisione del lavoro tra gli slaves:

Definizione del problema:
data una richiesta di generazione di un'immagine di dimensioni WxH e la Tabella qui sopra descritta, questo algoritmo restituisce l'elenco degli slaves da utilizzare e il numero di righe dell'immagine che ciascuno di essi deve calcolare.

Considerazioni preliminari:
il numero di righe da assegnare a ciascuno slave non può che basarsi sull'indicazione di carico contenuta nella Tabella. Questo non garantisce, qualunque algoritmo venga scelto, che la ripartizione del carico sia "equa". Alcune parti dell'immagine possono infatti richiedere un tempo molto superiore per essere calcolate rispetto ad altre.

Si sceglie di utilizzare sempre tutti gli slaves disponibili, evitando di suddividere tra più slaves il servizio di richieste con un costo inferiore a 100000 (piccole richieste possono verificarsi nel caso in cui uno slave fallisca e si debba ripartire il suo lavoro tra gli altri).

L'algoritmo ideale dovrebbe far sì che, dopo l'assegnazione del numero di righe da calcolare ai vari slaves, il carico di ciascuno slave fosse il medesimo.
L'algoritmo scelto NON garantisce questo, ma ha il pregio di essere molto semplice e quindi molto veloce. Considerando il fatto che la stima del costo di un calcolo è molto approssimata, utilizzare un algoritmo di ripartizione del carico più complicato non porterebbe a miglioramenti significativi nelle prestazioni del sistema.

Algoritmo:
Se il costo della richiesta è inferiore a 100000, viene assegnata allo slave con il valore più basso di carico presente nella Tabella. In caso contrario, si procede come segue:
La Tabella viene scandita e ne viene creata una copia in cui al posto del carico c'è il numero di righe da far calcolare allo slave corrispondente.
Sia CARICO_TOTALE la somma delle voci "carico" della Tabella e N il numero di righe della Tabella.
Detto Cj il carico corrente di uno slave, il numero di righe da assegnargli è dato dalla formula:

N_RIGHE = parte_intera( ( 1 - Cj / CARICO_TOTALE )  * H /  ( N -1 ) )

Ovviamente uno slave non viene utilizzato se, a causa dell'arrotondamento, si ha per esso N_RIGHE == 0.
Per evitare i problemi dovuti all'arrotondamento introdotto dalla formula, allo slave presente nell'ultima riga della Tabella viene imposto di calcolare le righe non ancora assegnate agli altri slaves.

Esempio:
La tabella 1 mostra una situazione in cui CARICO_TOTALE == 453,6E6
La richiesta di un'immagine 800x600 (con un numero massimo di iterazioni pari a 1000) genera le seguenti assegnazioni:

Tab. 2

nome host numero porta numero righe da calcolare
lia09 20000 183
lia07 20001 183
lia06 20001 234

Dopo la assegnazione, la Tabella viene aggiornata e la nuova situazione è indicata nella tab.3:

Tab. 3

nome host
numero porta carico
lia09 20000 323200000
lia07 20001 323200000
lia06 20001 287200000


PRESENTAZIONE| SPECIFICHE | BILANCIAMENTO DEL CARICO | TOLLERANZA AI GUASTI| ANALISI DELLE PRESTAZIONI | METODO DI CALCOLO | CONCLUSIONI