Il flusso di controllo interno dei processi

A completamento della presentazione

dell’algoritmo di base segue l’analisi del flusso di controllo interno dei moduli supervisore ed esploratore.

Si consideri inizialmente il modulo supervisore: la relativa implementazione in Linda è descritta in Fig. 5.4. Il codice proposto separa la fase di gestione centrale della ricerca (funzione master) dalle fasi di inizializzazione e terminazione della stessa (funzione

master_main). Tale decomposizione intende isolare la parte caratterizzante dell’algoritmo (la fase centrale di ricerca) dalle altre aventi

carattere generale e che non saranno inutilmente replicate nella successiva

presentazione di alcune varianti dell’algoritmo.

/* le costanti simboliche NEWPOS e QUIT identificano tipi di lavoro differenti dalla normale ricerca αβ di alberi di gioco: rispettivamente la ricezione di un nuovo albero e la terminazione del processo*/ #define NEW_POSITION -1

#define QUIT -2

int master_main(int n_worker,int depth) {

position *root,*successor;

int nmoves,minimax,i,master(),worker(); for (i=0;i<n_worker;i++)

eval ("worker",worker(depth)); /* creazione struttura di worker */

while (!end()) {

load_new_position (&root); /* un nuovo albero di gioco */

nmoves=genmoves(root,&successor); if (nmoves==0) /* non è necessaria nessuna ricerca? */

return(evaluate(root)); out ("root",*root); /* comunica ai worker il nuovo albero */

out ("sincr",n_worker); for (i=0;i<n_worker;i++)

out ("job",NEW_POSITION); /* richiesta di lettura del nuovo albero */

in ("sincr",0); /* il master prosegue solo dopo che tutti i worker hanno ricevuto

il nuovo albero */

minimax=master(n_worker,nmoves,depth,su ccessor); /* fase centrale della ricerca */

in ("root",*root); /* rimozione dell‘albero visitato */

}

for (i=0;i<n_worker;i++) {

out ("job",QUIT); /* comunicazione di terminazione dell‘elaborazione */

in ("worker", 0); /* la terminazione di un worker fa sì che la

relativa tupla attiva divenga passiva e quindi rimovibile dallo spazio delle tuple*/

} return (0); }

int master(int n_worker,int nmoves) {

int nmoves,local_score,subtree,free,best; local_score=-INFINITE; /* inizializzazione copia locale dello score */

out ("score", local_score); /* inizializzazione score globale */ free = n_worker;

subtree = 1;

while ((subtree <= nmoves) || (free<n_worker)) /* il ciclo termina quando sono stati

distribuiti tutti i lavori e recuperati tutti i risultati */

if ((subtree <= nmoves) && (free>0)) /* c‘è ancora lavoro da distribuire e almeno

uno degli esploratori è libero? */ {

out ("job",subtree); /*

inserimento in agenda di un lavoro di ricerca */

free--; subtree++; }

else /* attesa del completamento di almeno un lavoro */

{

in ("result",?value,?r_subtree); /* recupero di un risultato */

local_score=value; /* aggiornamento locale dello score */

in ("score",?int);

out("score",local_score); /* aggiornamento globale dello score */

best=r_subtree; }

free++; }

in ("score",?int); /* la tupla "score" va rimossa per non produrre effetti laterali

indesiderati nelle successive ricerche */

return (local_score); }

Fig. 5.4 Algoritmo base: flusso di controllo del processo master

La funzione master_main descrive una

successione ciclica di ricerche di alberi di gioco intendendo simulare così la situazione

generale che si verifica in una partita reale. Tale sequenza è preceduta da una fase iniziale in cui viene creata la struttura di processi

worker. In particolare viene creata una tupla attiva per ciascuno di essi; tale tupla innesca l’esecuzione asincrona della funzione worker (Fig. 5.5). Detta funzione ha un unico

parametro formale: la profondità nominale di ricerca; questo parametro di ricerca può essere già comunicato in questa fase perché assunto costante in tutte le ricerche. Normalmente nella lista di parametri formali è presente anche un identificatore (o nome) del generico worker che permette al master di stabilire, in situazioni eccezionali, interazioni di tipo simmetrico con esso. La sua assenza nella funzione worker evidenzia ancora maggiormente la completa indistinguibilità di questi processi.

Creazione e terminazione di processi sono attività computazionalmente costose; non appaiono quindi efficienti soluzioni che prevedono la creazione di una struttura di worker per ogni nuova ricerca. L’approccio corretto è invece che nella ricerca di tutti gli alberi di gioco venga utilizzata la stessa struttura di worker. In questo e molti altri domini è quindi certamente da preferire il progetto di un unico tipo di modulo worker con funzionalità generali, capace però di

specializzarsi quando necessario impedendo così di ricorrere ad una sua sostituzione

qualora l’elaborazione richieda una modifica dinamica delle funzioni ad esso richieste.

int worker(int depth) { position *root,*successor,*tree_pointer; int nmoves,subtree,score,value,job_type,quit,s; quit=false; while(!quit) { in ("job",?job_type); switch (job_type) {

case QUIT: /* fine */ quit=true; break;

case NEW_POSITION: /* la ricerca riguarda nuovo albero di gioco */

in ("position",?*root); in ("sincr",?s);

out ("sincr",s-1); nmoves=genmoves(root,&successor);

break;

default: /* il job riguarda una normale ricerca sequenziale αβ */

subtree=job_type; tree_pointer=successor+subtree-1;

makemove(tree_pointer); rd ("score",?score); /* aggiornamento score locale */

value=- alphabeta(tree_pointer,-INFINITE,-score,depth); out ("result",value,subtree); undomove(tree_pointer); break; } } return (0); }

Fig. 5.5 Algoritmo base: flusso di controllo di un processo worker

Nel caso di problemi di ricerca, qualora

esistano parametri che differenzino una ricerca dalla precedente, è ragionevole che la

comunicazione di questi (da master a worker) avvenga come una normale interazione mediata da scambio di tuple passive. Nell’algoritmo in esame tale interazione riguarda unicamente la comunicazione per diffusione del nodo radice del nuovo albero di gioco; essa avviene prima dell’inizio della ricerca. Si osservi come il master completi questa interazione sincronizzandosi con la ricezione di questa informazione da parte di

tutti i moduli worker. Punti di sincronizzazione come questo sono normalmente origine di inefficienza; il loro inserimento è però

necessario al fine di garantire la correttezza dell’algoritmo. Nel caso specifico

dell’implementazione di Fig. 5.4 le velocità relative dei processi potrebbero essere tali per cui, in assenza del punto di sincronizzazione, un modulo worker potrebbe ricevere un lavoro di ricerca prima della specifica dell’albero di gioco cui essa si riferisce.

La ricezione del nuovo nodo radice costituisce per i worker un lavoro di natura diversa rispetto alla normale ricerca αβ; lo stesso vale per la comunicazione di fine elaborazione formulata dal master una volta completato il ciclo di ricerche. In situazioni come questa di lavori con diverso significato come può il processo worker identificare il tipo di lavoro prelevato dall’agenda?

La soluzione generale in Linda è inserire nella tupla-lavoro un campo che ne indichi

esplicitamente il tipo. Nella presente implementazione è stata possibile

un’ottimizzazione: il tipo di lavoro e la sua descrizione occupano lo stesso campo della tupla-lavoro. I lavori di "lettura nodo radice" e "fine elaborazione" non sono infatti

accompagnati da descrizione; prevedendo per essi identificatori numerici diversi dai possibili valori che può assumere la descrizione del lavoro "ricerca αβ", l’identificazione di quest’ultimo tipo di lavoro avviene implicitamente per esclusione.

La fase ciclica della funzione master_main si chiude con la rimozione di tutte le tuple passive ancora presenti nello spazio omonimo.

Seppure non necessaria ai fini della ricerca (ormai completata), questa operazione è indispensabile nel garantire la correttezza: la presenza di tuple "spurie" potrebbe infatti creare interazioni indesiderate durante le successive ricerche.

Si consideri la funzione master; essa descrive la fase centrale di distribuzione e controllo della ricerca. Il flusso di controllo evidenzia l’intercalarsi durante la ricerca complessiva

delle due funzionalità predominanti del modulo master:

• creazione ed inserimento in agenda di un nuovo lavoro e

• ricezione di un risultato e conseguente gestione.

L’implementazione proposta dà priorità alla prima attività: viene generato un nuovo lavoro non appena un modulo esploratore si rende disponibile per la sua elaborazione.

L’informazione "numero di esploratori disponibili", seppure di natura globale ai moduli, viene gestita localmente dal

supervisore; egli, infatti, è in grado di dedurre che un esploratore non è più occupato dal verificarsi dell’evento "ricezione di un risultato". Il modulo supervisore è così in grado di

stabilire autonomamente quando inserire in agenda un nuovo lavoro: immediatamente dopo la ricezione di un risultato.

Il codice della funzione master descrive il procedere della ricerca attraverso tre fasi consecutive:

• start-up: è la fase iniziale in cui il master genera un numero di lavori pari a quello degli esploratori; quest’ultimi vengono quindi impegnati nella loro totalità fin dall’inizio della ricerca. Ad epilogo di questa attività il

supervisore si sospende nell’attesa della ricezione del primo dei risultati che saranno inseriti nell’omonima struttura dati distribuita. • fase intermedia: in questo stadio la ricezione di un risultato e la produzione di un nuovo lavoro di ricerca si alternano regolarmente. Questo comportamento del supervisore limita però il tempo di occupazione del generico esploratore il quale, dopo aver prodotto un risultato, è costretto ad attendere che esso sia ricevuto ed elaborato dal supervisore prima di poter disporre di un nuovo lavoro. Una

possibile soluzione a questo problema è rilasciare l’eccessivo accoppiamento supervisore-esploratore facendo sì che il numero medio L di lavori in agenda sia non nullo. Da un punto di vista implementativo è sufficiente che nella fase di start-up siano inseriti in agenda (L+Nw) lavori, dove Nw è il numero di esploratori. La costante L deve

essere dimensionata in modo da sopportare variazioni improvvise delle velocità relative dei moduli (ad es. esploratori che completano rapidamente la ricerca) o situazioni eccezionali (ad es. completamento simultaneo di più lavori); essa non può però superare certi valori di soglia a causa dei problemi di mancato ordinamento dei lavori ed overhead di ricerca che ne deriverebbero. Questo tipo di soluzione sarà tuttavia sperimentato nello studio dei metodi di decomposizione dinamica.

L’inefficienza presentata sarà invece eliminata con un approccio differente, applicato ad una delle varianti dell’algoritmo di base che

verranno presentate in seguito (cfr. 5.2.1.1.2).

• attesa finale: è la fase conclusiva in cui il supervisore, dopo avere distribuito la ricerca di tutti i sottoalberi al top-level, attende la

ricezione dei risultati degli ultimi lavori non ancora completati. Questa fase rivela una grave inefficienza: l’agenda di lavori rimarrà vuota fino alla fine della ricerca e quindi ogni esploratore diverrà definitivamente inoperoso dopo avere completato il proprio lavoro e ciò fino a che tutti gli altri non avranno terminato il rispettivo. Tale problema costituisce un caso particolare di distribuzione del carico non uniforme. I metodi di decomposizione statica soffrono inevitabilmente di questo problema, a meno che essi prevedano un’analisi statica del carico la quale permetta di programmare il completamento pressoché contemporaneo degli ultimi lavori (essa è comunque di non realistica attuazione per problemi di ricerca

αβ). I metodi con decomposizione dinamica, invece, risolvono in modo naturale i problemi della natura appena descritta.

Si consideri, infine, la funzione worker di Fig. 5.5 la quale descrive il flusso di controllo di un generico esploratore. Esso si sviluppa

attraverso il ciclico ripetersi delle operazioni: • estrazione di un lavoro dall’agenda

• identificazione del tipo di lavoro ricevuto e sua esecuzione.

Il codice proposto mette in risalto l’operazione di selezione del tipo di lavoro e separa in modo netto le azioni corrispondenti a ciascuna

classe; il dettaglio di quest’ultime è già stato implicitamente discusso.

Nel documento Indice generaleINDICE GENERALEIINTRODUZIONE1 (pagine 131-138)