I criteri di decomposizione

Ancora uno dei tre interrogativi iniziali deve essere risolto: in base a quali criteri è decisa la decomposizione o meno di un nodo dell’albero di gioco?

Considerazioni precedenti hanno dimostrato che la risposta a questa domanda è legata alla soluzione di un altro sottoproblema: stabilire se un nodo di cui un processore è supervisore deve essere esplorato dallo stesso processore oppure distribuito ad uno diverso. Questa decisione, operata autonomamente dal

supervisore, può essere descritta da un’unica funzione booleana; quest’ultima incorpora il criterio di decomposizione, cioè l’insieme di regole che determina i nodi di decomposizione e i particolari della loro decomposizione (cioè quali dei successori sono distribuiti nella rispettiva esplorazione).

Il criterio di decomposizione rappresenta la parte caratterizzante di un algoritmo di decomposizione: l’avere confinato questa componente in un’unica funzione booleana significa avere definito una struttura software estremamente flessibile, capace di ospitare facilmente qualsiasi algoritmo della classe in analisi (sia esso di tipo statico o dinamico). Come noto, l’applicazione del criterio di decomposizione da parte di un supervisore richiede conoscenza che può essere locale o globale a tale processore. L’acquisizione della conoscenza globale è, in termini di efficienza, molto più costosa. Poiché il numero di

invocazioni della funzione booleana di test è elevato (pari, in una ricerca, al numero di nodi visitati), un criterio di decomposizione

ragionevole deve limitare quanto possibile la necessità delle informazioni globali. L’idea generale è decomporre il criterio di

decomposizione in due sottocriteri,

rispettivamente applicati alle porzioni locale e globale della conoscenza di cui esso

necessita. Il criterio "locale" ha la funzione di filtrare quei nodi che, indipendentemente dallo stato globale della ricerca, non è conveniente esplorare in parallelo; l’acquisizione della

conoscenza globale e l’applicazione del sottocriterio relativo hanno luogo solo

nell’ipotesi che il sottocriterio locale "approvi" l’eventuale distribuzione del sottoalbero in esame.

In questa porzione di albero non puo` avvenire distribuzione della ricerca

I nodi di questa sezione possono essere decomposti

D

Thresold

DThresold è la profondità minima perche` possa avvenire la distribuzione

Fig. 5.17 Sottocriterio di decomposizione basato sulla dimensione del sottoalbero

Sono ora elencati alcuni esempi di sottocriteri locali:

• sottocriteri basati sulle dimensioni del

sottoalbero: vengono esclusi dalla distribuzione sottoalberi di piccole dimensioni in quanto l’entità del degrado indotto dalla ricerca parallela (in particolare quello dovuto alle comunicazioni) fa preferire in questi casi la visita sequenziale. La determinazione della dimensione di soglia non è realisticamente ottenibile con metodi analitici perché ciò richiederebbe un troppo complesso studio quantitativo delle forme di degrado; la tecnica più semplice è quella empirica del

"trial-and-error" che procede per

approssimazioni successive della soluzione migliore.

La misura più corretta delle dimensioni di un albero è il numero di nodi; purtroppo questa informazione non può essere nota prima che la visita αβ abbia inizio. È comunque possibile stimare con buona approssimazione il numero di nodi che saranno visitati conoscendo la

profondità dell’albero e la larghezza della finestra αβ iniziale [Bau78b]: il costo del calcolo di tale stima non è comunque

trascurabile poiché include operazioni come l’elevamento a potenza e la radice.

Una soluzione più semplice è approssimare le dimensioni dell’albero con la sua profondità [Eli90]: ciò induce una partizione dei nodi in due sottoinsiemi come illustrato in Fig. 5.17. • il criterio "young-brothers-wait" [FMMV89]: questo è il primo di una serie di criteri finalizzati a ridurre l’overhead di ricerca; tali criteri hanno significato solo nell’ipotesi di alberi (almeno parzialmente) ordinati. Il criterio stabilisce che il primo successore di un nodo deve essere completamente valutato prima che possa avere inizio la visita dei successivi. Il dato locale necessario per applicare questo metodo è l’ordine di visita I (rispetto ai suoi "fratelli") del nodo N in esame: se I=1, allora il nodo deve essere valutato dal suo supervisore (e quindi non distribuito). Si osservi come in questa eventualità è garantito che la decomposizione dei fratelli sia presa in considerazione solo dopo l’avvenuta valutazione di N.

Una naturale generalizzazione di questo metodo è che sia impedita la distribuzione dei primi K (K≥1) successori; la valutazione di questi nodi avverrà dunque in sequenza. In questo caso la condizione sufficiente ad

impedire la distribuzione del nodo è: I>K, dove I è l’indice ordinale del nodo cui è applicato il criterio.

La giustificazione del criterio è che se i nodi interni dell’albero di gioco sono ordinati, allora con elevata probabilità la migliore mossa è individuata da uno dei nodi più a sinistra; visitare completamente i sottoalberi relativi a tali nodi prima di affidare i successivi ad altri processori significa ottenere una finestra αβ

migliore per la ricerca di quest’ultimi.

• limitazione del numero di successori visitati in parallelo: si intende limitare il massimo

parallelismo ottenibile localmente alla decomposizione di un nodo. Lo scopo di questo approccio è anch’esso di limitare il problema dovuto al fatto che le ricerche di successori successivi non usufruiscano dei

risultati di visite iniziate precedentemente, ma ancora incomplete. Anche per questo controllo è necessario un dato esclusivamente locale al supervisore: il numero di nodi la cui ricerca è stata da esso distribuita, ma dei quali non è stato ancora restituito il risultato.

I seguenti criteri, invece, sono basati su conoscenza globale:

• limitazione del numero di lavori in attesa di essere eseguiti. Si consideri la struttura logica complessiva di tutti i lavori (come appare ad un generico worker): il criterio intende limitare il numero massimo di lavori che possono essere ospitati in essa; lo scopo è ridurre l’overhead di sincronizzazione. Infatti se le richieste di

servizio fossero in numero eccessivo rispetto al numero di serventi, ciò determinerebbe

un’attesa eccessiva da parte dei richiedenti. Nel caso del presente algoritmo tale attesa sarebbe concentrata nella fase finale della decomposizione di un nodo quando, stabilita per tutti i successori la distribuzione o la visita sequenziale (già completata), il supervisore si sincronizza nella ricezione di tutti i risultati non ancora comunicati. Un valore tipico per la dimensione massima della struttura di lavori è il numero totale di processori. L’informazione globale coinvolta in questo criterio è il numero di nodi presenti nell’agenda generale.

L’implementazione in Linda prevede a riguardo la definizione di una variabile distribuita con funzione di contatore, incrementata dal

supervisore che distribuisce un nuovo lavoro e decrementata dal worker che completa

l’estrazione di uno di essi.

• distribuzione solo se esiste almeno un nodo inoperoso (idle): il criterio previene l’eccessiva permanenza di un lavoro in agenda e quindi riduce anch’esso l’overhead di

sincronizzazione poiché minimizza il tempo che intercorre fra la domanda di un servizio e il completamento di questo. In questo caso l’informazione globale è il numero di processori inoperosi; la relativa implementazione in Linda è analoga a quella descritta per il contatore di lavori in agenda.

5.2.2.2.4 Un chiarimento delle finalità