PROGETTO OBBLIGATORIO 1.
GAME OF LIFE ...... (è talmente parallelo da essere imbarazzante).
Questo esempio venne introdotto dal matematico John Conway nei primi anni 70 del secolo scorso.
Per dettagli e una buona descrizione preliminare guardate la pagina di wikipedia : http://en.wikipedia.org/wiki/Conway's_Game_of_Life
E' l'esempio che a aperto un intero campo di ricerca quello degli Automi Cellulari.
Supponiamo di avere una matrice (2D ma possiamo pensare anche a un caso a 3D) di celle che possono avere solo 2 stati vive o morte, 1 e 0.
Al tempo 0 la matrice ha uno stato casuale di celle 1 e 0. Il tempo procede per intervalli finiti e l'evoluzione dello stato di ogni cella dal tempo t al tempo t+1 è determinato solo dalle 8 celle che la circondano con le seguenti regole:
Se una cella ha stato 1:
Se meno di 2 celle vive la circondano muore di solitutine.
Se più di 3 celle vive la circondano muore per sovraffollamento.
Se una cella ha stato 0:
Se è circondata da 3 celle vive nasce per riproduzione.
Notate che questo tipo di problema può essere parallelizzato sia come divisione di dati assegnando a ciascun processo/thread una parte della matrice che come divisione di task dato che l'evoluzione degli stati è dipendente solo dallo stato delle singole celle.
Per Esempio in figura vedete l'evoluzione di una parte della matrice in base alle regole date. Le frecce rappresentano alcune operazioni di aggiornamento di stato mentre la linea rossa una delle possibili divisioni di dati fra diversi "Processing Elements" siano questi thread che processi. Notate come ciascuna operazione di aggiornamento sia indipendente dalle altre. Questo tipo di caso rientra fra gli "automi cellulari paralleli" o sincroni proprio per questo motivo. Hanno grande importanza in moltissime applicazioni simulazioni di ambienti, sistemi complessi e soluzione di equazioni differenziali alle derivate parziali.
Un'altra classe di automi cellulari è quella asincrona, usata, per esempio per creare modelli di reti di calcolatori.
Esempio di comunicazione di ghost cells in una distribuzione di dati 2D. Porzioni adiacenti di matrice so scambiano i dati relativi alle colonne confinanti. Se considerassimo una struttura di tipo isoperiodico allora anche le colonne estremale sarebbero confinanti fra loro così come la riga superiore e inferiore. La topologia diverrebbe quella di un Toro.
Un esempio molto promitivo di scambio di colonne lo trovate in questo codice.
Poi l'includere una delle ghost cells appena riempite nel trasferimento delle righe confinanti (vedi la riga verde ) evita di dover fare una comunicazione in più per le celle in angolo.
