I risultati sperimentali hanno sottolineato i riflessi sull’efficienza del mancato impiego nella ricerca αβ
del processore destinato all’esecuzione del processo supervisore. Non disponendo di strumenti in Linda per il controllo dell’allocazione dei processi, il recupero "produttivo" del tempo in cui il supervisore è sospeso in attesa del completamento di un esploratore deve essere programmato esplicitamente. A riguardo sono presentate due differenti soluzioni.
5.2.1.2.1 Un approccio intuitivo
Si vuole applicare all’algoritmo base di
decomposizione l’idea seguente: una volta che è stato distribuito lavoro sufficiente ad
impegnare tutti gli esploratori, il modulo supervisore esegue il lavoro relativo al primo sottoalbero della radice non ancora distribuito; solamente dopo aver completato tale compito esso sarà nuovamente assegnato alle sue mansioni di supervisione. Durante la fase di ricerca il supervisore diviene a tutti gli effetti un esploratore: l’architettura logica di
comunicazione di Fig. 5.1 deve essere dunque modificata per tenere conto di questa nuova situazione (Fig. 5.7).
Supervisore Esploratore1 Esploratore2 Esploratore(N-1)
Supervisore
Fig. 5.7 Architettura logica di
comunicazione con impiego nella ricerca del processo supervisore
Le modifiche apportate al modulo supervisore sono trasparenti ai moduli esploratori il cui flusso di controllo rimane invariato rispetto alla prima versione dell’algoritmo base. Esse sono inoltre confinate nella fase centrale della
ricerca che per il modulo supervisore è descritta dalla funzione master in Fig. 5.8.
#define update_local_and_global_score\ {\ local_score=value;\ in ("score",?int);\ out ("score",local_score);\ best=r_subtree;\ }\
int master(int n_worker,int nmoves,int depth,position *successor)
{
int nmoves,local_score,subtree,free,best; local_score=-INFINITE;
out ("score", local_score); free=n_worker;
subtree=1;
while ((subtree <= nmoves) || (free<n_worker)) if (subtree<=nmoves)
{
if (free>0) /* si distribuisce lavoro appena un worker è libero*/
{ out ("job",subtree); free--; subtree++; } else { if (inp ("result",?value,?r_subtree)) /* si testa se un esploratore
ha completato il suo lavoro */ free++; else /* invece di sospendersi nell‘attesa dei
risultati degli esploratori il supervisore
diviene lui stesso esploratore */ { tree_pointer=successor+subtree-1; makemove(tree_pointer); value=- alphabeta(tree_pointer,-INFINITE,-local_score,depth); undomove(tree_pointer); r_subtree=subtree; } if (value>local_score) update_local_and_global_score; /* la gestione dei risultati è realizzata dalla stessa porzione di codice,
indipendentemente dal fatto che essi siano prodotti dagli esploratori o dal supervisore */
} }
else /* attesa finale del completamento degli ultimi lavori */
{
in ("result",?value,?r_subtree); if (value>local_score)
update_local_and_global_score; free++; } in ("score",?int); return (local_score); }
Fig. 5.8 Impiego nella ricerca del supervisore: un approccio intuitivo
Il codice in Linda evidenzia la priorità che il modulo supervisore assegna alla gestione dei lavori rispetto alla sua nuova attività di
esploratore: quest’ultima è infatti intrapresa solo se:
• (free==0): è stato distribuito un numero di lavori sufficiente ad impegnare tutti gli esploratori e
• (inp("result",?value,?r_subtree)==false): nessun esploratore ha completato la sua ricerca
Il modulo supervisore implementa in modo diverso rispetto agli esploratori le fasi iniziale e finale dell’esecuzione di un lavoro: il prelievo di quest’ultimo e la comunicazione del relativo risultato non sono infatti mediati da strutture dati distribuite; lo scambio logico di queste informazioni avviene all’interno dello stesso modulo e non è quindi necessaria alcuna interazione sullo spazio delle tuple.
I dati statistici di Tab. 5.2 descrivono i risultati della sperimentazione di questa nuova
versione dell’algoritmo base.
nr. proc T (sec) N (nodi) S E Fpm SO VR (nodi/sec) Svr
1 8301 5347545 --- --- --- --- 644 ---3 4544 5860668 1.83 0.61 0.70 0.10 1290 2.00 5 3173 6330053 2.62 0.52 0.66 0.18 1995 3.10 7 2779 6867688 2.99 0.43 0.61 0.28 2471 3.84 9 2517 7310806 3.30 0.37 0.57 0.37 2905 4.51 11 2310 7990369 3.59 0.33 0.54 0.49 3459 5.37
Tab. 5.2 Sperimentazione dell’impiego nella ricerca del supervisore
L’approccio proposto si è rivelato fallimentare: il confronto con la prima versione dell’algoritmo base evidenzia una notevole riduzione dello speedup, maggiormente visibile con
La spiegazione di risultati tanto deludenti è ancora una volta suggerita dall’esame del fattore di produzione Fpm il quale evidenzia un tempo di utilizzo troppo esiguo delle risorse di elaborazione. Con 11 processori, ad esempio, si ha Fpm=0.54: ciò significa che un generico processore è stato inoperoso durante il 46% del tempo complessivo di ricerca. Tali valori possono essere giustificati solo da una
strategia di distribuzione dei lavori inefficiente. Un modulo esploratore che produce un
risultato durante la fase centrale della ricerca diviene inoperoso fino a che il supervisore non rileva questo evento e produce di conseguenza un nuovo lavoro. Nella nuova versione
dell’algoritmo il modulo supervisore è
impegnato per la maggior parte del suo tempo di elaborazione nella ricerca di sottoalberi e le funzioni di supervisione possono solo
intercalarsi fra una ricerca e la successiva; a causa del suo duplice compito il supervisore non è in grado di rilevare prontamente il completamento di un altro lavoro: ciò avverrà solo dopo che avrà terminato il suo lavoro corrente. Pertanto un generico esploratore verrà sospeso per un tempo che in media è pari alla metà del tempo medio di ricerca di un sottoalbero della radice.
Per effetto dell’aumentata inoperosità dei processori si è però avuta una diminuzione dell’overhead di ricerca. I due parametri sono infatti direttamente collegati: il fatto che i moduli esploratore si sospendano più a lungo in attesa dell’attribuzione di un nuovo lavoro aumenta la probabilità che quest’ultimo non inizi prima che anche altri esploratori abbiano completato il proprio e possa così beneficiare dell’eventuale aggiornamento dello score da essi prodotto.
Il miglioramento dell’overhead di ricerca è comunque irrisorio rispetto all’entità del problema legato all’eccessivo inutilizzo dei processori. In conclusione il confronto fra i due algoritmi proposti vede dunque vincente la prima versione evidenziando così come la rinuncia di un processore alla ricerca sia comunque conveniente se ciò comporta un
elevato bilanciamento del carico fra i moduli worker.