Il ruolo di GnuChess nella tesi

Nel seguito della tesi GnuChess costituirà un utile strumento ai fini implementativi e sperimentali delle idee che saranno presentate ed approfondite nei Capitoli 5 e 6. In particolare, nell’ambito

dell’approfondimento degli algoritmi paralleli di ricerca operato nel Capitolo 5, esso sarà utilizzato alla stregua di una libreria di

funzioni. Gli algoritmi che saranno presentati in quella sede, infatti, pur essendo indipendenti dal dominio di applicazione, fanno

tuttavia riferimento a funzionalità classiche di gestione dell’albero di gioco (generazione di mosse, esecuzione e retrazione di una

mossa, valutazione statica dei nodi terminali, ecc.) le quali sono inerentemente dipendenti dal dominio. Poiché il progetto e la realizzazione di queste funzionalità esula dagli obbiettivi di questo

lavoro, esse saranno prelevate integralmente dal codice di

GnuChess. Quest’ultimo, tuttavia, non è una libreria di funzioni, ma un programma di gioco finalizzato alla minimizzazione di

ridondanze e costi computazionali in nome di una massimizzazione delle prestazioni: in virtù di queste esigenze la sua struttura non è perfettamente modulare e quindi ci si dovrà attendere qualche difficoltà nella "estrazione" delle funzionalità di nostro interesse prima citate; tali eventuali impedimenti saranno eventualmente denunciati nel Capitolo 7 in sede di commento conclusivo. Nel Capitolo 6, invece, GnuChess rivestirà un duplice ruolo. In particolare esso sarà impiegato nello sviluppo di un giocatore parallelo costituito dalla replica di sue istanze. L’unica differenza fra tali istanze di GnuChess sarà la conoscenza terminale in esse incorporata e quindi la rispettiva funzione di valutazione. Solamente questa sezione del suo programma sarà dunque modificata (tra l’altro in minima parte), mentre il resto della sua struttura rimarrà inalterato.

Le prestazioni del giocatore parallelo così ottenuto saranno valutate sulla base della sua qualità di gioco: GnuChess costituirà, quale avversario, un valido banco di prova di tali performance.

Capitolo 3

Linda

3.1 Introduzione

Linda è un linguaggio di coordinazione caratterizzato da poche semplici operazioni basate sul paradigma di programmazione parallela chiamato comunicazione generativa. Linda non è un linguaggio di programmazione completo [CarGel90]: esso va piuttosto interpretato come un insieme di oggetti ed operazioni (su essi definite) inteso per essere integrato con un linguaggio di programmazione preesistente (linguaggio di base). Il risultato di tale estensione è dunque un "dialetto" del linguaggio di base arricchito con costrutti per descrivere e controllare la concorrenza. La classificazione più appropriata per Linda è di linguaggio di coordinamento, cioè finalizzato alla gestione ed alla coesione in unico programma di più attività separate.

È più corretto pensare a Linda come ad un modello di

programmazione parallela piuttosto che ad un reale supporto alla concorrenza: Linda può essere istanziato (implementato) in

molteplici modi e contesti dipendenti, ad esempio, dall’architettura del sistema (uniprocessore, multicalcolatore, rete locale di

calcolatori, ecc.) o dal linguaggio di base. Particolare attenzione sarà rivolta nel seguito all’analisi di una di tali istanze del modello Linda: il sistema Network C-Linda per reti di workstation [Lin90]; questo è il supporto reale utilizzato per lo sviluppo e la

sperimentazione delle idee e degli algoritmi oggetto del presente lavoro.

Ciò che distingue un linguaggio di coordinazione da uno sequenziale è la disponibilità di costrutti per la creazione ed il coordinamento (comunicazione + sincronizzazione) di più flussi di esecuzione (processi).

Linda è un modello di creazione e coordinamento di processi ortogonale al linguaggio di base in cui è incorporato: non ha interesse cosa e come computa ciascun flusso di esecuzione, bensì solo il modo con cui tali flussi (visti dunque come scatole nere) sono creati ed è permesso loro di cooperare.

Il modello su cui si fonda Linda prende il nome di comunicazione generativa. Se due processi devono comunicare, essi non

scambiano messaggi (modello ad ambiente locale) o condividono una variabile (modello ad ambiente globale); al contrario, il

processo mittente della comunicazione genera un nuovo oggetto (chiamato tupla) che deposita in una regione accessibile ed esterna a tutti i processi (chiamata spazio delle tuple). Il processo

destinatario è così in grado di accedere a tale area per prelevare la tupla e quindi con essa il contenuto della comunicazione. La

creazione dei processi è trattata alla stessa maniera: un processo che intende creare un secondo processo concorrente genera una

"tupla attiva" che affida allo spazio delle tuple. Una tupla attiva esegue una sequenza di computazioni indipendente dal processo che l’ha generata, per poi trasformare se stessa in una tupla ordinaria (passiva).

Un’implicazione di questo modello è che comunicazione e

creazione di processi sono due aspetti della stessa operazione: per creare un processo viene generata una tupla attiva che si

trasformerà in una passiva, mentre nella comunicazione viene generata direttamente una tupla passiva. In entrambi i casi si ottiene lo stesso risultato: lo spazio delle tuple viene arricchito con un nuovo oggetto che potrà essere acceduto da qualsiasi processo interessato ad esso.

Altra proprietà rimarchevole del modello è che i dati sono scambiati nella forma di oggetti persistenti (e non di messaggi transitori). Il destinatario della comunicazione, infatti, oltre a rimuovere la tupla generata dal mittente può anche accedere ad essa senza

"consumarla", cioè permettendo che essa rimanga nello spazio delle tuple dove anche altri processi potranno leggerla.

Linda permette di organizzare collezioni di tuple in stutture dati distribuite, cioè strutture accessibili simultaneamente da più

processi. L’unificazione prima descritta fra la creazione dei processi e dei dati significa che si può organizzare collezioni di processi in strutture dati attive [CarGel88]: ogni processo componente la struttura dati attiva è un flusso di computazione al cui termine diviene un elemento della struttura dati passiva che è ritornata come risultato della computazione complessiva.

Le implicazioni del modello di comunicazione generativa si estendono oltre la programmazione parallela: il modello intende essere applicato ad altre forme di comunicazione che non siano la sola cooperazione fra processi dello stesso programma parallelo. Lo spazio delle tuple si presenta come un flessibile meccanismo anche per la comunicazione fra programmi scritti in linguaggi diversi, o fra un programma-utente ed il sistema operativo, oppure ancora fra un programma ed una futura versione di se stesso [CarGel89].

Lo spazio delle tuple esiste indipendentemente dalle computazioni dei programmi (visti come scatole nere), siano essi primitive di sistema o programmi-utente scritti in un linguaggio qualsivoglia. Le attuali implementazioni di Linda, tuttavia, concentrano per il

momento l’attenzione sulla sola comunicazione fra processi di uno stesso programma parallelo.

Le pagine seguenti offriranno una presentazione più accurata del modello di programmazione distribuita basato sullo spazio delle tuple; seguirà la descrizione di C-Linda e una caratterizzazione dello stile di programmazione in Linda con alcuni esempi di implementazione di strutture dati distribuite e di interazione fra i processi. Ad epilogo di questa sezione saranno prodotti alcuni cenni sulle tecniche di realizzazione di Linda, con particolare

attenzione all’implementazione su architetture parallele con memoria distribuita.