Generazione degli alberi

La generazione degli skeleton trees che compongono il dataset si basa sulle regole di riscrittura viste nella Sezione 1.1.2. In particolare, è stata utilizzata una libreria, RPL-Shell [8], per il design di applicazioni parallele basate su skeleton trees. La libreria mette a disposizione un oggetto seq_wrapper che funge da contenitore alle porzioni di codice sequenziale che l'utente vuole usare. Una volta incorporato il codice sequenziale nell'oggetto seq_wrapper, essi vanno importati in una shell. Qui si procede al design vero e proprio, con gli strumenti messi a disposizione da RPL-Shell, che verrà descritto in maniera dettagliata. Un esempio di utilizzo della shell è mostrato in Figura 3.1.

Annotazione

In un primo momento vengono scelti casualmente gli skeleton sequenziali da inserire nell'albero, prendendoli dalle misurazioni eettuate (Sezione 3.2.2). In questa fase vengono specicate alla shell informazioni che saranno utili in fase

Figura 3.1: Un esempio d'uso di RPL-Shell per la generazione dei samples [8]. Vengono evidenziate le varie fasi, descritte nella Sezione 3.2.3.

di ottimizzazione. In particolare, dopo aver importato il codice sequenziale, viene specicata la dimensione dello stream in input, il tempo di servizio dei sequenziali scelti, ed il limite di risorse utilizzabili, che chiameremo in questa sede parallelismo potenziale.

Più precisamente, il massimo numero di core che ciascuno skeleton tree può utilizzare viene determinato casualmente, in modo da bilanciare programmi con eccesso e difetto di parallelismo (Sezione 3.1). Per i programmi eseguiti su Ninja, il grado di parallelismo massimo è limitato a 32 core. Per quelli eseguiti su Phiask, avendo meno risorse a disposizione, tale limite è ssato a 12. Il codice relativo alla procedura è evidenziato in verde in Figura 3.1.

Applicazione delle regole di riscrittura

In questa fase, evidenziata in rosso in Figura 3.1, vengono applicate le regole di riscrittura della Sezione 1.1.2. Usando la notazione della Grammatica 1 (Se- zione 1.1), gli alberi di partenza su cui si è scelto di applicare le regole sono i seguenti:

• farm(seq), che genera 3 riscritture; • pipe(seq, seq), che genera 6 riscritture;

• pipe(seq, pipe(seq, seq)), che genera 15 riscritture;

• pipe(seq, pipe(seq, pipe(seq, seq))), che genera 32 riscritture;

Lo scopo di questa scelta è di ottenere dierenti composizioni degli skeletons in modo da riprodurre correttamente tutto lo spazio di ottimizzazione, per rende-

Pipe

Pipe

Sk Sk

Sk

(a) pipe (pipe (Sk, Sk), Sk).

Pipe

Sk Pipe

Sk Sk

(b) pipe (Sk, pipe (Sk, Sk)).

Figura 3.2

re il dataset un sottoinsieme rappresentativo delle istanze di cui interessano le predizioni.

Dalle regole create vengono rimosse quelle derivanti dalla Regola 4 (Sezio- ne 1.1.2, associatività della pipeline). Le regole create con RPL-Shell infatti ammettono arietà della pipeline pari a due, e quindi applicando la Regola 4 vengono generate le regole corrispondenti agli alberi in Figura 3.2. Tuttavia, per aumentare la Markovianità del task, che aiuta l'apprendimento della TreeE- SN, è stato deciso di non limitare l'arietà degli skeleton trees, ammettendo così alberi con un numero di gli arbitrario. Con questa assunzione, gli alberi in Figura 3.2 corrispondono però allo stesso programma, visibile in Figura 3.3, che sarebbe così ridondante, giusticando la rimozione. Avere arietà massima degli

Pipe

Sk Sk Sk

Figura 3.3: pipe (Sk, Sk, Sk).

alberi pari a 2 (come avveniva nella tesi [1]) può creare dipendenze "ttizie" tra i nodi discendenti dell'albero, che abbattono la Markovianità del task [5]. Ottimizzazione

Dopo l'applicazione delle regole di riscrittura, gli skeleton trees generati non sfruttano ancora adeguatamente il numero di risorse disponibili (per esempio il numero di worker delle farm è sempre pari ad uno, di default). Come visto in fase di annotazione, ogni programma viene etichettato con il parallelismo potenziale, ovvero il massimo numero di risorse ad esso assegnabili. Le ottimizzazioni (blu in Figura 3.1) sono utili per determinare il parallelismo eettivo di ciascun nodo dell'albero, tenendo conto del tempo di servizio del nodo, e rispettando il parallelismo potenziale assegnato all'intera applicazione. In dettaglio vengono eseguite tre ottimizzazioni:

• Farmopt: Con essa si assegnano risorse alle farm proporzionalmente alla durata dei loro tasks. Infatti, in accordo con l'Equazione (1.2), il numero di workers delle farm viene scelto come

N w = max{1, Tcal}.

Si noti che questa ottimizzazione non tiene conto del parallelismo poten- ziale, e del numero di risorse utilizzate dagli altri nodi.

• Max resources: Come si è visto nel paragrafo precedente, dopo l'appli- cazione delle regole di riscrittura gli alberi non sono ancora congurati per sfruttare le risorse disponibili. Deniamo ricorsivamente il grado di parallelismo di uno skeleton algoritmico Sk come

N (Sk) =          1 Sk = Seq P#stages i N (Ski) Sk = P ipe(Sk1, . . . , Sk#stages)

maxi≤#stages{N (Ski)} Sk = Comp(Sk1, . . . , Sk#stages)

Nw∗ N (Sk) + 2 Sk = F arm(Sk)

(3.1) Si vede dalla formula che l'unico parametro libero su cui intervenire è il numero di workers delle farm. Considerando un generico albero t conte- nente n farm, il grado di parallelismo ottimo Noptsi calcola come il mas-

simo numero di workers assegnabile contemporamente alle farm presenti nell'albero rispettando il limite di risorse disponibili Navailable:

root(t) = Sk =⇒ Nopt= max N w1,...,N wn

N (Sk)≤Navailable

{N (Sk)}

dove Navailable è il parallelismo potenziale dell'albero t. In Figura 3.1 si

può notare come dopo l'applicazione delle ottimizzazioni, tutti gli alberi generati hanno numero di risorse assegnate inferiore o pari a 32 (come stabilito dalle annotazioni nella parte evidenziata in verde). Ne segue che i workers della farm vengono assegnati proporzionalmente al carico computazionale, rispetto agli altri nodi dell'albero.

• Pipeopt: con questa ottimizzazione si cercano di ottenere delle pipeli- ne bilanciate (sempre in accordo con l'analisi delle performaces fatta in Sezione 1.2). Se nell'albero c'è un nodo pipe che ha uno degli stadi mol- to più lento rispetto agli altri, si cercano di "compattare" gli altri stadi (introducendo un nodo comp) per ridurre lo sbilanciamento.

Generazione del codice

Per generare il codice C++ che implementa gli skeleton trees, viene usata ancora RPL-Shell. In particolare, a ciascun albero dev'essere fornito un produttore di dati di input, lo streamer, ed un consumatore per i risultati prodotti, il drainer. A tale scopo, lo skeleton tree viene incorporato nel secondo stage di una pipe, come illustrato in Figura 3.4.

L'input prodotto dallo streamer consiste, come visto precedentemente, in 1000 matrici elaborate poi dal programma parallelo, e deallocate dal drainer. Le

Streamer Skeleton Tree Drainer

Figura 3.4: Architettura delle applicazioni FastFlow [11] generate mediante RPL-Shell per la creazione del dataset.

funzionalità tipiche di un paradigma di programmazione parallela basato su patterns (Sezione 1.1), quali i vari tipi di skeletons, la possibilità di comporli, ed il mapping dei threads sui processori per rispettare il limite di risorse assegnate, vengono fornite ad RPL-Shell dalla libreria FastFlow [11].