I risultati sperimentali

In questa sezione sono presentati ed analizzati i risultati della sperimentazione dell’algoritmo base applicato al dominio degli scacchi.

Tale algoritmo e tutti i successivi che verranno presentati saranno sottoposti agli stessi test di valutazione delle prestazioni; questa scelta permetterà immediati confronti. Le

considerazioni che seguiranno riguardo l’organizzazione degli esperimenti devono quindi intendersi di carattere generale.

L’algoritmo verrà impegnato nella esplorazione di posizioni di test; in particolare è stato scelto l’insieme di 24 posizioni di Bratko-Kopec [BraKop82] (riportato integralmente in Appendice A). Si tratta di posizioni

appositamente ideate per valutare la qualità di gioco di un giocatore automatico di scacchi. Deve essere chiaro, tuttavia, che questa sperimentazione intende stimare unicamente l’efficienza dell’algoritmo distribuito e non la qualità delle sue scelte; quest’ultima, infatti, dipende pesantemente dalla conoscenza del dominio confinata nella funzione di valutazione e la cui analisi esula dagli scopi di questa sezione.

La finalità principale degli esperimenti è quella di confrontare le prestazioni dell’algoritmo distribuito con quelle della sua versione sequenziale. L’algoritmo base di

decomposizione sarà confrontato ovviamente con l’algoritmo αβ. Alcuni degli algoritmi paralleli presentati in seguito conterranno euristiche per il miglioramento della ricerca: il loro algoritmo sequenziale di riferimento sarà in tal caso alphabeta arricchito delle stesse euristiche.

La sperimentazione degli algoritmi è accompagnata dalla raccolta di parametri statistici con i quali si intende porre in risalto vari aspetti della dinamica della loro

esecuzione.

I parametri più importanti per la valutazione di un programma parallelo riguardano i tempi di elaborazione. Essendo l’architettura hardware costituita da una rete di workstation, cioè

macchine multiutente e quindi non

completamente dedicate all’esecuzione di un’unica applicazione, classifichiamo i possibili tempi di elaborazione in:

• tempo reale (o assoluto): misura la durata effettiva degli esperimenti, quale cioè apparirebbe ad un osservatore umano che assistesse al loro evolversi;

• tempo di macchina (o di CPU): misura il tempo realmente dedicato dalla macchina agli esperimenti, "depurando" così il tempo reale delle frazioni in cui la macchina serve altri utenti.

Data la visita di una generica posizione di test, il parametro temporale più interessante è il tempo complessivo T di ricerca dell’albero di gioco ad essa associato.

Per l’algoritmo sequenziale il tempo di ricerca è misurato come l’intervallo che intercorre fra l’invocazione al top-level della funzione ricorsiva αβ ed il suo completamento. Le prestazioni dell’algoritmo sequenziale costituiscono il metro di valutazione degli algoritmi distribuiti e quindi la loro misura non può essere influenzata dalle condizioni di carico (per loro natura variabili) della macchina su cui essa è operata. Per questo motivo il tempo complessivo T viene misurato come tempo di macchina.

Il tempo di ricerca dell’algoritmo parallelo viene misurato dal processo master: esso è

l’intervallo fra l’inizio della distribuzione del nuovo nodo radice e l’acquisizione del suo valore minimax finale.

Per gli algoritmi paralleli è molto difficoltoso l’utilizzo del tempo di macchina quale metrica: ciò richiederebbe l’analisi dei tempi macchina di ogni workstation impegnata nella ricerca ed una loro complessa sintesi in unico dato statistico. Il tempo di ricerca verrà dunque misurato come tempo reale; questa scelta non pregiudica la validità degli esperimenti poiché essa comporta un’approssimazione per difetto dell’effettivo valore degli algoritmi paralleli22. Il confronto fra l’algoritmo parallelo e la sua versione sequenziale viene sintetizzato dallo speedup (o guadagno) S, inteso come rapporto tra il tempo complessivo Ts di ricerca

sequenziale ed il tempo complessivo Tp

impiegato dalla versione parallela sullo stesso albero di gioco:

S = ^TS TP

Lo speedup S è un indice assoluto indicante il guadagno in termini di velocità computazionale introdotto dalla sostituzione dell’algoritmo sequenziale con una sua versione parallela. Altro parametro assoluto è l’efficienza relativa E; esso normalizza lo speedup S rispetto al numero di processori impiegati:

E = ^S

N= ^TS

TP⋅N

L’efficienza relativa è utile quale misura del degrado complessivo delle prestazioni; essa infatti scaturisce dal confronto fra il guadagno reale e quello ideale.

I parametri statistici sin qui definiti sono di tipo generale ed utilizzati come metriche standard nella valutazione dell’efficienza di algoritmi paralleli. La loro definizione intende

implicitamente che i processori sono identici. Ciò che in generale avviene quando

l’architettura hardware è costituita da una rete locale è che le risorse di elaborazione sono eterogenee e quindi con prestazioni differenti. In questo contesto le prestazioni degli algoritmi sequenziale e parallelo sono difficilmente confrontabili attraverso i parametrici statistici S ed E. Per tenere conto di questa situazione il calcolo del tempo complessivo di ricerca T deve essere corretto di un fattore che dipende dalle velocità relative di elaborazione delle singole macchine:

• sia l’insieme di processori P={P1,P2,...,PN} e Pr∈P un processore di riferimento;

• sia vi la velocità di elaborazione23 del processore Pi (i=1..N);

• ad ogni processore è associato un peso di che esprime la velocità relativa di elaborazione rispetto al processore Pr:

di= ^vi vr

(i = 1..N)

fc= ^N di i=1 N

∑

• Dato il tempo di ricerca complessivo T, il valore che sarà effettivamente assunto per questo parametro è:

fc⋅T

Il fattore medio di produzione Fpm è un parametro che permette di valutare l’effettivo impiego produttivo dei processori durante il tempo complessivo T di ricerca; esso è così definito:

• sia N il numero totale dei processori e Tp_i

(i=1..N) il tempo dedicato dall’i-esimo processore ad attività produttiva, cioè

all’esecuzione di lavoro del tipo "ricerca αβ"; • la media aritmetica Tpm dei singoli contributi Tp_i (i=1..N) esprime il tempo che in media un processore dedica alla ricerca; il fattore medio di produzione normalizza questo parametro rispetto alla durata T della ricerca costituendo così un indice assoluto:

Fpm= ^Tpm T = Tpi i=1 N

∑

T

Nell’algoritmo di base proposto il modulo

master non esegue attività produttiva e quindi il suo tempo di produzione è nullo. In questo caso particolare verrà riportato anche il tempo medio di produzione dei soli moduli worker (Fpmw), così da isolare il comportamento eccezionale del master.

Il parametro Fpm consentirà di stimare il bilanciamento del carico indotto dall’algoritmo parallelo; è infatti tale proprietà ad influire maggiormente sull’utilizzo produttivo dei processori. Più in generale esso darà indicazioni sull’incidenza complessiva dei degradi legati alla sincronizzazione ed alla comunicazione.

Altro importante dato statistico è la dimensione della ricerca; essa è quantificata dal numero totale N di nodi dell’albero visitati

(interni+terminali).

Il confronto fra le dimensioni della ricerca sequenziale (Ns) e parallela (Np) permette di stimare l’overhead di ricerca OR:

OR =^Np Ns

−1

Parametro tipico di un algoritmo di ricerca è la misura VR della quantità di ricerca elaborata nell’unità di tempo (velocità di ricerca):

VR =^N T

Anche per questo parametro è possibile il confronto fra la sperimentazione nel sequenziale e nel parallelo; a riguardo è calcolato un indice assoluto analogo allo speedup:

• siano VRs e VRp rispettivamente le velocità di ricerca sequenziale e parallela;

• si definisce guadagno di velocità Svr il parametro:

Svr= ^VRp VRs

Nell’ipotesi realistica di overhead di ricerca non negativo vale la relazione: Svr≥S. Si osservi, infatti, che sul valore dell’indice Svr non incide l’overhead di ricerca; esso consente quindi di isolare e valutare gli effetti delle altre forme di degrado delle prestazioni.

La sperimentazione effettiva dell’algoritmo di base è stata preceduta da una serie di test di verifica delle velocità di elaborazione delle singole workstation. Ciascuna di esse è stata impegnata nella ricerca sequenziale con profondità 5-ply della posizione nr.1 di Bratko-Kopec; quale indice della velocità di elaborazione è stata considerata la velocità di ricerca (espressa in nodi/sec). Questi test hanno evidenziato una limitata eterogeneità delle 11 macchine a disposizione (SUN 4) evidenziando una partizione delle stesse in due gruppi di macchine omogenee (la

differenza relativa di prestazioni di workstation appartenenti allo stesso gruppo è inferiore al 5%):

• 8 workstation (compresa quella di riferimento) meno veloci;

• 3 workstation con velocità di elaborazione superiore di un fattore 1.7 alla macchina di riferimento.

Questi dati consentono di calcolare il fattore di correzione del tempo complessivo di ricerca; tale valore è funzione di numero e tipo di

workstation impiegate nella ricerca parallela. Ad esempio nel caso di sperimentazione con tutte le 11 macchine esso è costante:

fc= vi vr i=1 N

∑

N = ^{8⋅1+3⋅1. 7} 11 ≅1.19

Un parametro della ricerca di alberi di gioco è la sua profondità nominale. Per tutti gli

esperimenti essa è stata fissata a 5-ply. Le motivazioni di questa scelta sono duplici: la sperimentazione su profondità inferiori appare non significativa date le limitate dimensioni dell’albero, mentre la scelta di profondità maggiori di 5-ply è resa proibitiva dai tempi eccessivi necessari al suo completamento. Tutti gli algoritmi paralleli implementati sono parametrici rispetto al numero di processori impiegati nella ricerca. L’esplorazione delle posizioni di Bratko-Kopec verrà ripetuta con diversi valori di questo parametro, così da tracciare la dipendenza funzionale dei

parametri statistici rispetto ad esso. Lo studio della loro variabilità permetterà inoltre di anticipare il comportamento dell’algoritmo in presenza di un numero di processori ancora maggiore del massimo a disposizione per l’esecuzione di questi esperimenti.

Per motivi di spazio non sarà riportato il dettaglio dei parametri statistici calcolati per ogni posizione di test, bensì una loro naturale generalizzazione basata sulla somma dei tempi di ricerca e del numero di nodi visitati nel ciclo di esplorazione di tutte le posizioni.

Alcune considerazioni di carattere teorico intendono spiegare quali valori di efficienza si devono attendere dalla sperimentazione di tale algoritmo:

• l’efficienza dell’algoritmo base è

proporzionale al rapporto B/Nw fra il fattore di diramazione dell’albero di gioco ed il numero di esploratori [MarCam82];

• per un albero di gioco con valore tipico B=40, una ricerca sequenziale αβ è equivalente ad una ricerca esaustiva (algoritmo minimax) di un albero con fattore B=7 di diramazione [Gil72]. Pertanto, se l’algoritmo di decomposizione fosse sperimentato su un’architettura di Nw=40

esploratori, lo speedup medio che si dovrebbe ottenere è 7.

In Tab. 5.1b è presentato il risultato della sperimentazione dell’algoritmo base di decomposizione, mentre in Tab. 5.1a è

spiegato il significato delle colonne di Tab. 5.1b (tale legenda avrà valore anche per le

successive tabelle).

nr. proc il numero complessivo di processori (master+worker)

T ^{il tempo complessivo di ricerca (misurato in secondi) necessario}

alla esplorazione di tutte le 24 posizioni di test

N ^{il numero totale di nodi visitati nella ricerca di tutte le posizioni di}

test

S ^{lo speedup (}= ^T1 Tnr. proc)

E ^{l’efficienza relativa (}= ^S nr. proc⁾

Fpm il fattore medio di produzione

Fpmw il fattore medio di produzione dei worker

SO ^{l’overhead di ricerca (}=^{Nnr . proc} N1 −1)

VR ^{la velocità di ricerca (}=^N T⁾

SVR il guadagno di velocità (= ^{VRnr. proc} VR1 )

Tab. 5.1a Sommario dei parametri statistici

nr. proc T(sec) N (nodi) S E Fpm Fpmw SO VR (nodi/sec) Svr

1 8301 5347545 --- --- --- --- --- 644 ---3 4571 5754203 1.82 0.61 0.66 0.98 0.08 1259 1.95 5 2770 6599460 3.00 0.60 0.75 0.93 0.23 2382 3.70 7 2242 7236560 3.70 0.53 0.71 0.83 0.35 3228 5.01 9 1988 7876769 4.18 0.46 0.68 0.77 0.47 3962 6.15 11 1786 8521288 4.65 0.42 0.66 0.73 0.59 4771 7.41

Tab. 5.1b Algoritmo base di

decomposizione: sperimentazione

Il dato statistico più rilevante è rappresentato dai valori molto bassi dello speedup. Il motivo di prestazioni tanto deludenti risiede nella forte incidenza complessiva delle forme di degrado; il parametro E (efficienza relativa) spiega inoltre come essa sia tanto maggiore quanto più elevato è il numero di processori.

L’esame in dettaglio di ciascuna forma di degrado evidenzia una diversa variabilità in funzione del numero di processori:

• overhead di ricerca: l’aumento della quantità di nodi visitati procede di pari passo con quello dei processori; il degrado maggiore è stato infatti ottenuto dalla versione dell’algoritmo con 11 processori che ha visitato il 59% di nodi in più rispetto all’algoritmo sequenziale.

L’incidenza di questa forma di degrado sulle prestazioni è notevole: si confrontino a riguardo i valori dello speedup S e i rispettivi guadagni Svr nella velocità della ricerca; quest’ultimo dato statistico può essere interpretato come lo speedup che si sarebbe ottenuto in assenza di overhead di ricerca. I dati statistici relativi alla ricerca con 11

processori, ad esempio, rivelano una perdita di efficienza del 37% causata da questa forma di degrado (Svr=7.41 >> S=4.65).

L’entità del degrado si rivela molto elevata se confrontata con valori tipici di altri algoritmi. La causa di tale comportamento è dovuta alla minima condivisione: i moduli esploratori cooperano (con mediazione del supervisore) solamente all’inizio ed alla fine della propria ricerca (rispettivamente aggiornando la copia dello score e comunicando il risultato della ricerca). Durante la fase centrale è dunque loro negata la possibilità di fruire dei risultati

prodotti dagli altri esploratori, inducendo così una ricerca più svantaggiosa rispetto

all’algoritmo sequenziale dove la ricerca di un sottoalbero può avvalersi dei risultati di tutte le ricerche precedenti (Fig. 5.6).

tempo

in questo intervallo di tempo si completano k ricerche

durata della (i-k)-esima ricerca

inizio (i-k)-esima ricerca _{inizio i-esima ricerca} fine (i-k)-esima ricerca

Nell‘ipotesi che la (i-k)-esima ricerca migliori il valore corrente dello score, la i-esima ricerca non potra` usufruire di questo miglioramento poiche` gia` iniziata.

La ricerca sequenziale non soffre di questo problema perche` la i-esima ricerca ha inizio solo dopo che sono terminate tutte le ricerche (i-k) con k>0.

Fig. 5.6 Dipendenza dell’overhead di ricerca dalle velocità relative dei processi

Perché l’overhead di ricerca è funzione crescente del numero di processori?

La ricerca αβ trae beneficio dal calcolo quanto più immediato di un elevato valore parziale dello score; il suo valore iniziale è -∞ e con esso avranno inizio le visite dei primi Nw sottoalberi della radice (Nw è il numero di esploratori): è evidente il degrado rispetto alla ricerca sequenziale dove già la visita del secondo sottoalbero potrà contare su una buona approssimazione del valore ottimo dello score (quella calcolata dalla ricerca del primo sottoalbero). Il fenomeno non riguarda solo la ricerca dei sottoalberi iniziali: in generale la maggiore distribuzione aumenta anche la probabilità che una ricerca Ri non benefici del miglioramento dello score prodotto dalla ricerca Ri-k (attivata precedentemente) proprio perché Ri ha avuto inizio prima che Ri-k fosse completata.

• overhead di sincronizzazione e

comunicazione: il fattore medio di produzione Fpm fornisce indicazioni su queste forme di degrado. Si osservi lo strano andamento di questo fattore in funzione del numero di

processori: crescente fino a 5 processori (75%) e poi decrescente fino a 11 dove si ottiene lo stesso fattore acquisito con 3 processori

(66%). Si confrontino questi valori con il fattore di produzione medio riferito ai soli esploratori il quale presenta andamento costantemente decrescente. La causa della discordanza fra la variabilità dei due parametri di produzione è l’attività non produttiva (dal punto di vista della ricerca αβ) del modulo supervisore. Esso svolge sole mansioni di coordinatore e per la maggior parte del tempo complessivo di ricerca T è sospeso in attesa di interagire con gli esploratori: questa situazione è tipica in implementazioni basate sul modello master-worker. Nell’ipotesi (finora assunta implicitamente) che ogni modulo sia allocato su un processore diverso, in virtù dell’elevato tempo di sospensione del supervisore si viene a creare un forte inutilizzo del processore che lo ospita. Soluzione immediata a questo problema è che il supervisore ed uno degli esploratori siano allocati sullo stesso processore. Tuttavia tale soluzione è non descrivibile nello standard di Linda essendo l’allocazione dei processi trasparente al programmatore; si consideri, inoltre, che il paradigma master-worker opera

efficientemente solo se il master è in grado di generare lavoro velocemente in modo da tenere occupati tutti i worker: se esso condividesse il tempo di CPU con un altro processo i suoi tempi di risposta potrebbero essere così rallentati da influire sensibilmente sulle prestazioni complessive.

All’aumentare del numero di esploratori la rinuncia alla produttività del processore che ospita il supervisore diviene meno influente; per contro, cresce il numero medio di

esploratori inattivi durante la fase finale della ricerca (il fattore Fpmw è infatti decrescente). Sono questi i motivi di degrado che affliggono maggiormente la produzione: la loro

combinazione giustifica l’andamento non monotono del fattore Fpm. Il costo delle comunicazioni incide invece sulla produzione in modo costante e trascurabile: il numero di interazioni fra moduli sono infatti in numero esiguo (proporzionale al fattore di diramazione dell’albero) ed indipendente dalla quantità di processori.

Nel documento Indice generaleINDICE GENERALEIINTRODUZIONE1 (pagine 138-148)