I parallel design pattern sono stati introdotti nei primi anni ’00 con l’obiet- tivo di fornire soluzioni a problemi paralleli ricorrenti. Rappresentano un modo ingegnerizzato di considerare il problema connesso allo sfruttamento del parallelismo. Un design pattern `e una rappresentazione di un problema comune con una soluzione efficiente e collaudata per quel problema. Compa- iono usualmente nella programmazione ad oggetti anche se l’idea `e generale e pu`o essere applicata a differenti modelli di programmazione. Un pattern
in questo ambito non `e un vero e proprio costrutto ma consiste in un “buon modo” (un consiglio) per strutturare la propria applicazione, il programma- tore che segue tale “consiglio” otterr`a un’applicazione pi`u facile da riusare e da mantenere. Un parallel design pattern `e descritto da un preciso insieme di elementi, il cui significato `e qui spiegato:
• problem: il problema da risolvere;
• context : il contesto dove il pattern pu`o essere opportunamente usato; • forces: le differenti caratteristiche che influenzano il parallel design
pattern;
• solution: una descrizione di una o pi`u soluzioni possibili al problema risolto dal pattern.
Uno degli aspetti pi`u interessanti relativi ai parallel design pattern `e che questi partizionano lo spazio di progettazione in quattro parti:
• finding concurrency: include i parallel design pattern che modellano differenti generi di attivit`a parallele o concorrenti che possono essere usate in un’applicazione parallela;
• algorithm structure: contiene i parallel design pattern che modellano i ricorrenti pattern degli algoritmi paralleli;
• supporting structure: include i parallel design pattern che possono essere usati per implementare i pattern del livello precedente;
• implementation mechanisms: contiene i pattern che modellano i mec- canismi di base usati per implementare un’applicazione parallela.
L’importanza di tale struttura di progettazione risiede sulla separazione dei problemi: il programmatore dell’applicazione lavorer`a nei primi due livelli e quindi nel dominio dell’applicazione ignorando difatti l’architettura uti- lizzata. Viceversa, il programmatore di sistema lavorer`a negli ultimi due livelli.
4.3
Pattern pool evolution
Tale pattern `e stato proposto ed introdotto in FastFlow, come spiegato in [4], perch´e cattura differenti contesti di utilizzo. Quelli legati agli algoritmi evolu- tivi e quelli legati a computazioni simboliche. Come visto nella sezione 4.2, lo spazio di progettazione pu`o essere diviso in quattro parti: finding concurrency che modella i differenti tipi di attivit`a parallele/concorrenti che possono essere usate nell’applicazione parallela, algorithm structure che modella i differenti algoritmi ricorrenti, supporting structure che include i pattern usati per im- plementare quelli del livello precedente e per finire l’implementation mecha- nisms che modella i meccanismi base usati per implementare un’applicazione parallela.
Il pool evolution, visto che modella un ben preciso algoritmo parallelo, appartiene al secondo spazio di progettazione elencato. Questo pattern non solo `e utile a rappresentare algoritmi genetici ma anche tutte quelle appli- cazioni che, per fornire un risultato, iterano l’applicazione di determinate funzioni, nella fase di evoluzione, (che siano crossover, mutazioni o che dir si voglia) fino al verificarsi di una qualche condizione di terminazione. L’idea `e quindi illustrata dal seguente pseudocodice:
begin
while not(termination(Pop) and iterations ≥ 0) do tmpPop = selection(Pop);
newPop = evolution(tmpPop); Pop = Pop S filter(newPop); end while
end
`
E quindi un processo iterativo in cui l’i -esima iterazione lavora su ci`o che `
e computato dall’iterazione (i-1)-esima. Evidenziamo le caratteristiche pe- culiari di questo processo:
• Pop: `e l’input che viene sottoposto alla fase di selezione ed i cui ri- sultati sono sottoposti ad evoluzione al fine di evolvere verso una po- polazione “migliore” newPop, che meglio si adatta alle caratteristiche che l’ambiente gli richiede. Tale popolazione subisce un filtraggio e l’output si integra o no (a seconda della strategia seguita) con parte della popolazione iniziale per andare a formare l’input dell’iterazione successiva;
• selection: `e una funzione che identifica gli individui che devono sot- toporsi alla fase di evoluzione. Pu`o essere implementata utilizzando, per esempio, la funzione identit`a oppure una qualsiasi altra funzione, che predilige un individuo ad un altro in base al valore di uno o pi`u attributi, etc...;
• Evolution: racchiude tutti gli operatori necessari a modificare e quin- di garantire l’evoluzione della popolazione. E embarassingly paral-`
lel in quanto un solo individuo od un gruppo di questi pu`o evolvere indipendentemente dagli altri selezionati;
• filter : `e anch’essa una selezione, crea la nuova popolazione per l’itera- zione successiva filtrando in base a qualche parametro (valore di fitness per esempio). Si possono utilizzare diverse tecniche. Per esempio: all’insieme sottoposto ad evoluzione si possono integrare gli individui dell’iterazione precedente (i genitori), oppure si possono creare nuovi individui, o si pu`o decidere di ridurre la dimensione della popolazione considerando solo l’output dell’evoluzione, etc. . . ;
• termination: verifica che le condizioni di terminazione siano soddisfat- te, il tal caso si arresta il processo di evoluzione. La terminazione `e generalmente implementata in modo sequenziale.
In questo pattern `e possibile sviluppare l’applicazione personalizzando i com- portamenti delle varie fasi, infatti: `e possibile effettuare la fase di selection e/o quella di filter sequenzialmente parallelizzando la sola evolution oppure una od entrambe queste fasi possono essere parallelizzate, utilizzando op- portunamente l’implementazione del parallel for (sezione 4.4) presente in FastFlow, ottenendo una sequenza di farm. La selection e la filter possono essere viste come delle vere e proprie MapReduce. Nella selection, per esem- pio, in fase di map si valutano gli elementi ed in fase di reduce si filtra in base a ci`o che si desidera. Map e MapReduce sono implementate utilizzando il pattern ParallelForReduce (vedi sezione 4.4) che permette la paralleliz- zazione efficiente di parallel for e parallel for con riduzione, implementato utilizzando un farm con feedback. Ovvero un farm il cui emitter E schedula i task ai worker che eseguono il loro calcolo e spediscono l’output nuovamente all’emitter E.
Nella filter, si possono utilizzare diverse tecniche in base al problema affron- tato. In caso di stagnazione `e possibile, per esempio, rimpiazzare alcuni individui generandone di nuovi o clonando i migliori della popolazione attua- le. Altrimenti si possono semplicemente integrare gli individui dell’iterazione i -esima con quelli ottenuti applicando gli operatori di evoluzione a questi, unendo cos`ı figli e genitori per l’iterazione successiva.
Un altro aspetto da considerare riguarda la dimensione della popolazione. Alcuni algoritmi genetici lavorano con popolazione di dimensione costante mentre altri tendono a modificare la dimensione durante le iterazioni. La gestione di tale situazione `e lasciata al programmatore che usa il pattern, `e infatti compito suo gestire eventuali allocazioni o deallocazioni di memoria.
Il pattern pool evolution `e fornito con due costruttori (mostrati in figu- ra 4.3): uno che supporta l’esecuzione stand-alone dello stesso, processando solo la popolazione di input specificata come parametro; l’altro che supporta l’esecuzione su popolazioni che appaiono sullo stream di input. Inoltre, ad un’istanziazione della classe poolEvolution `e possibile associare un ambiente esterno di tipo env t contenente tutte le informazioni globali necessarie alle varie fasi descritte dell’intero processo ed interamente personalizzabile dal- l’utente a seconda delle richieste dell’applicazione. Il tipo env t `e passato come parametro del template e l’oggetto ambiente `e passato al costruttore del pool.
/∗ c o n s t r u c t o r : t o b e u s e d i n non−s t r e a m i n g a p p l i c a t i o n s ∗/ p o o l E v o l u t i o n ( s i z e t maxp , /∗ maximum p a r a l l e l i s m d e g r e e i n a l l p h a s e s ∗/ s t d : : v e c t o r <T> &pop , /∗ t h e i n i t i a l p o p u l a t i o n ∗/ s e l e c t i o n t s e l , /∗ t h e s e l e c t i o n f u n c t i o n ∗/ e v o l u t i o n t e v o l , /∗ t h e e v o l u t i o n f u n c t i o n ∗/ f i l t e r i n g t f i l , /∗ t h e f i l t e r f u n c t i o n ∗/ t e r m i n a t i o n t term , /∗ t h e t e r m i n a t i o n f u n c t i o n ∗/ const e n v t &E = e n v t ( ) ) ; /∗ u s e r ’ s e n v i r o n m e n t ∗/ /∗ c o n s t r u c t o r : t o b e u s e d i n s t r e a m i n g a p p l i c a t i o n s ∗/ p o o l E v o l u t i o n ( s i z e t maxp , /∗ maximum p a r a l l e l i s m d e g r e e i n a l l p h a s e s ∗/ s e l e c t i o n t s e l , /∗ t h e s e l e c t i o n f u n c t i o n ∗/ e v o l u t i o n t e v o l , /∗ t h e e v o l u t i o n f u n c t i o n ∗/ f i l t e r i n g t f i l , /∗ t h e f i l t e r f u n c t i o n ∗/ t e r m i n a t i o n t term , /∗ t h e t e r m i n a t i o n f u n c t i o n ∗/ const e n v t &E = e n v t ( ) ) ; /∗ u s e r ’ s e n v i r o n m e n t ∗/
Figura 4.3: Costruttori del pattern pool evolution di FastFlow.