HG – Grafo sincrono e confronto con INTEL TBB flow.

Abbiamo visto nel post precedente un primo esempio su come costruire un grafo di calcolo con la libreria HG. In questo post miglioreremo il codice già proposto e faremo un confronto con il codice per scriveremo con la libreria INTEL TBB flow.
Il codice è molto simile all’esempio precedente, l’unica differenza è che ora il nodo di ingresso non compie alcun lavoro, lasciando ai nodi dipendenti il compito di calcolarsi i punti su cui calcolare l’integrale. Questa modifica dovrebbe permettere un leggero miglioramento delle performance, dato che il grafo è completamente sincrono, nell’esempio precedente si attendeva che il nodo di ingresso calcolasse tutti i dati prima che i nodi dipendenti iniziassero il loro calcolo.

Per cui la funzione calcolata dal nodo di ingresso è:

Semplicemente l’input viene immediatamente passato come output. Da notare che il tipo di comunicazione è di tipo broadcast, cioè tutti i nodi dipendenti riceveranno lo stesso messaggio.
Mentre ai nodi dipendenti viene assegnato questa funzione:

Le linee evidenziate sono quelle aggiunte, che erano precedentemente svolte dal nodo di ingresso. Il resto del codice è identico.

Vediamo come possiamo trasporre questo codice usando la INTEL TBB flow.

Come prima impressione si ha un’idea di un codice più compatto, per il resto la composizione del grafo di calcolo è pressoché la stessa. Viene creato un nodo iniziale di tipo broadcast_node (linea 55), che viene poi connesso ad un layer di nodi di calcolo (linee 62-65). Successivamente si effettuerà il calcolo di somma dei vari integrali. Questo avviene direttamente nel main thread e non in un nodo dedicato, come nel caso dell hetereogeneous_graph.
La scelta è dovuta che per fare un’aggregazione si deve stabilire a compile time quali saranno e, soprattutto, quanti saranno i nodi da cui arriveranno gli inputs. Dato che io ho mantenuto questa scelta a run-time devo ovviare come detto precedentemente.

Per finire voglio fare una premessa: dato che ho lavorato per poco tempo sulla libreria TBB flow, può essere che il mio codice non sia proprio la soluzione ottimale, nel qual caso, accetterò volentieri ogni critica (motivata).

Saluti,
mik

HG – Primo esempio

Vediamo ora un primo esempio di utilizzo della mia libreria. Il codice sottostante serve per calcolare l’integrale di una semplice funzione. Dato che l’integrazione è solo un pretesto per vedere l’utilizzo della libreria, useremo il sistema più semplice per calcolare un’approssimazione di un integrale di una funzione continua: suddivideremo l’intervallo di integrazione in sotto intervalli piccoli, per ciascuno di questo valuteremo il valore della funzione in modo da poi calcolare l’area del rettangolo. Sommando successivamente le aree di ciascun rettangolo avremo la stima dell’integrale iniziale.

Il codice sorgente

Analizziamo ora il codice che implementa questo semplice calcolo. Dato che vogliamo utilizzare il multithreading, effettueremo una doppia suddivisione. La prima suddivisione avverrà per numero di thread, e poi ogni thread effettuerà la suddivisione fine di cui abbiamo precedentemente.

La struct info_job, è la struttura preposta a portare le informazioni al job le informazioni necessarie per svolgere il suo compito. Alla linea 37 abbiamo la creazione dell’ambiente dove il nostro grafo di calcolo verrà eseguito. All’interno dell’ambiente è possibile registrare delle risorse (di sistema). Di default è registrata un’unica risorsa che rappresenta il processore con i cuoi core logici.
Per chi ha un po’ di dimestichezza con la boost::graph, le linee di codice successive alla 42 non sono nuove. Viene creato un vettore di coppie dove ciascuna coppia rappresenta un collegamento tra un nodo e l’altro.
Alla linea 48 viene inizializzato il nostro grafo di calcolo.
Successivamente viene inizializzato ciascun nodo dandogli, in questo caso, tramite una lambda function il proprio job di calcolo.
Vediamo in dettaglio:

Il nome della funzione è init_node e prende un parametro template che informa il grafo su che tipo di nodo stiamo inizializzando. In questo caso è di tipo sincrono, cioè i nodi che dipendono da lui potranno iniziare il loro lavoro solo dopo che questo avrà finito completamente la sua esecuzione.
I parametri della funzione sono:
1. il nodo da inizializzare.
2. la funzione che deve essere eseguita. Questa funzione ha una signature ben precisa. Il primo parametro è un vettore che rappresenta l’input della funzione, mentre il secondo è l’ambiente.
3. il grafo di calcolo di cui il nodo fa parte.
4. l’ambiente dove verrà eseguito.
Senza entrare nel dettaglio della funzione calcolata, è da notare l’utilizzo di due funzioni speciali:
– unmarshall. Restituisce il primo elemento del vettore data e lo casta al tipo desiderato.
– marshall_vector. Restituisce un tipo generico che il grafo può gestire contenente un vettore di info_job opportunamente elaborato.

Dopo aver impostato le varie funzioni che il nostro grafo dovrà eseguire si può lanciare l’esecuzione del nostro grafo, chiamando la funzione run.
Questa funzione prede tre parametri, come possiamo vedere alla linea 115:
– Il primo è l’input iniziale che deve essere elaborato.
– Il secondo è il grafo stesso.
– Infine, il terzo è l’ambiente nel quale il grafo viene eseguito.
Inoltre la funzione prende anche due parametri template, il primo è il tipo del parametro di input (si potrebbe omettere), mentre il secondo è il tipo dell’output.

Abbiamo così analizzato il primo esempio di grafo costruito col heterogeneous graph.

A presto,
Mirko

Heterogeneous Graph su github.

Ciao a tutti, breve aggiornamento oggi sono riuscito a mettere su github una prima versione della mia libreria “Heterogeneous Graph”.
La libreria è fornita insieme a CMakeLists per poterlo compilare con il sistema che preferite.

Ecco il link: https://github.com/m1rku5/heterogeneous_graph

Buon divertimento,
mik

Call_once e gli altri?

Un altro dubbio mi è venuto sulla call_once. Come funziona? Quando hai una serie di thread che stanno correndo felici in parallelo e poi hai una porzione di codice che vuoi venga eseguito solo una volta da uno di essi, puoi utilizzare la call_once, collegata con una variabile once_flag.
Il dubbio che mi è venuto è il seguente: quando un thread sta eseguendo la funzione chiamata dalla call_once che succede agli altri thread? La risposta più ovvia è che rimangono in attesa, dato che molto spesso la call_once viene utilizzata per l’inizializzazione di risorse. Ma sarà davvero cosi?

Quello che sue è il codice che dovrebbe chiarire la cosa:

E’ piuttosto semplice, ci sono 4 thread, inizializzati con un numero progressivo per distinguerli, che eseguono una semplice funzione al cui interno c’è una call_once, il cui unico scopo è quello di segnalarci quale thread ha vinto la gara. Successivamente il thread viene sospeso per capire cosa accade agli altri. Un possibile ouptut è il seguente:

Dato che il cout non è sincronizzato, l’output è piuttosto confuso, ma a noi interessa che non appaia un ‘<‘ prima della comunicazione del vincitore. E per quante volte lo lanciate questo non accadrà mai. Volete provare ok lo potete fare cliccando su questo link.

Saluti,
mik

Lambda e variabili

Oggi post semplice su un dubbio che mi è venuto ieri. Data la mia scarsa familiarità con le lambda, mi sono chiesto quando il valore di una variabile passata per valore o per riferimento viene catturato.
Ma vediamo il codice sorgente:

La funzione r prende tutte le variabili per riferimento, tranne j che la prende per valore. La funzione c prende tutto per valore. Dato che le uniche variabili sono i e j, l’unica differenza tra le due funzioni è che r prende i per riferimento. Dopo avere definito le funzioni, cambio i valori delle variabile i e j e chiamo le funzioni, ecco l’output:

Questo è il link se volete provare. Come è ovvio, ma per me non lo era troppo, solo la variabile i, presa per riferimento ha il valore aggiornato.

baci,
mik

Heterogeneous Graph

Dopo le vacanze natalizie riprendiamo, ma questa volta lasciamo da parte lo standerd e parliamo di concorrenza e multithreading.
Alcuni anni fa ho iniziato a sviluppare una libreria che permettesse di gestire vari task concorrenti in modo semplice, gestendo le dipendenze tra di essi. La libreria si chiama Heterogeneous Graph. E’ basata sulla boost graph, dove ogni nodo è un’intà di calcolo e gli archi rappresentano le dipendenze.
Come già detto in precedenza ricorda in qualche modo la TBB flow, anche se ci sono delle sostanziali differenze.

L’idea iniziale

In principio la mia idea era di costruire una libreria che potesse eseguire i vari task sia in locale (in multitrading, usando una thread pool), sia in remoto su altre workstation (grid computing). Per questo la cominicazione tra nodi era stata pensata facendo un trasferimento di stringhe. Inoltre sfruttamndo il meccanismo dei future/promise, il fatto che due nodi fossero legati da una dipendenza non richiede necessariamente che il secondo non potesse essere mandato in esecuzione insieme al suo predecessore.

La comunicazione

Oltre a prevedere un meccanismo di esecuzione sincrono o asincrona, ogni task prendeva in input un vettore di stringhe, dove ogni elemento era l’output di uno dei nodi da cui dipendeva, era ripettato l’ordine con cui erano stati connessi i nodi. Avevo previsto anche le dovute funzioni di marshaling/unmarshaling.

Evoluzione

In questi ultimo periodo ho rivisto questa idea, perchè non volevo appesantire gli eventuali programmi che utilizzano principalmente, se non esclusivamente, il multithreading. Inoltre la costuzione di un grid computing è questione piuttosto complessa che mi aveva portato via molto tempo senza essere riuscito ad arrivare a niente di concreto. Così ho deciso di abbandonarla, almeno momentaneamente, per riprenderla nel momento in cui il resto della libreria sia a regime.
Inoltre la prima implementazione era stata realizzata in c++03, appoggiandomi alla Boost per le varie astrazioni di thread e sincronizzazione. Con l’arrivo dei nuovi standard ho deciso di rivederla completamente per cercare di riuscire di rompere la dipendenza dalla Boost.

Sorgenti ed esempi

Nei prossimi giorni vedrò di pubblicare i sorgenti in qualche repository pubblico, ed inoltre pubblicherò una serie di esempi che permettano di capire il suo utilizzo. Inoltre proverò, ove possibile, a fornire una implementazione parallela utilizzando la Intel TBB flow, per confrontare sia le prestazioni, sia per vedere la semplicità d’uso.

Futuri sviluppi

Per lavoro mi sono imbattuto sia nella librariea TBB sia nell’MPI, dal loro studio ho avuto modo di riflettere sulle loro differenze ed ho pensato a quali idee sarebbe interessante portare nella mia. Inoltre mi piacerebbe renderla interoperabile anche con la grid di DataSynapse.

Bye,
mik

Breve introduzione a Knights Landing

Oggi mol di testa, e quindi vado di articolo introduttivo a quella che è la nuova architettura proposta da Intel per l’hpc. Precedentemente Intel aveva proposto un coprocessore (Knights Corner) da affiancare al processore tradizionale. Qui invece si parla di processore vero e proprio. Si parla (almeno per la macchina che mi è arrivata) di circa 64 processori, ciascuno dei quali con capacità ci gestire 4 thread (hyperthreading).
Inoltre il processore è affiancato da circa 16GB di memoria MCDDR, che può essere configurata o come cache o come memoria allocabile, oppure in maniera ibrida.
Senza scendere troppo nei dettagli che potete trovare in siti specializzati se non direttamente da Intel, volevo fornirvi qualche impressione nel breve periodo per cui ho avuto modo di lavorarci.

Primo contatto

Appena arrivata e dopo una prima configurazione effettuta dall’IT, ho incominciato ad esplorare il contenuto software fornito. Praticamente niente!
Un CentOS 7.2 e stop. La suite Intel Parallel Studio XE 2017 (update 1), deve essere scaricata dal sito dopo aver registrato la macchina con il codice allegato.
Sarà la mia scarsa dimistichezza con linux, fatto sta che ho dovuto lanciare l’installazione diverse volte, perchè ogni volta non trovava qualche libreria di sistema che non veniva fornita di default.
Dopo un po’ di sudo (non solo digitato), sono riuscito ad arrivare in fondo all’installazione. Pensavo che la suite prevedesse anche una IDE stile (Visual Studio), anche se la mia precedente esperienza con il compilatore Intel mi aveva messo qualche dubbio. In effetti su linux Intel si affianca ad Eclipse, se volete usarlo all’interno di una IDE (su windows invece su Visual Studio).

Compilazione

A questo punto inizio a compilare, adatto i miei CMake al nuovo compilatore ed inizio a lanciare compilazioni sulla nostra libreria.
Non vi travio con le varie operazioni di adattamento che sono stato costretto a fare per arrivare in fondo a questo nuovo passaggio; mai detto fu più vero quale: “Nuovo compilatore che usi, nuovi problemi che trovi”.

Primi risultati

Mai lanciare una compilazione su questo genere di macchine senza effettuare una rigorosa analisi del codice. I primi risultati non potranno che risultare a dir poco deprimenti. Fa impressione di poter lanciare 256 thread che lavorare effettivamente in parallelo, ma il solo clock della macchina 1.4GHz, toglie subito ogni possibilità di ottenere buone performance.

A domani per altri info.

mik

Point of declaration

Direttamente collegato alla ODR (One Definition Rule), si trova il point of declaration, che non è altro che il punto in cui una variabile, una classe o una funzione sono dichiarati.
Per esempio per un nome il punto di dichiarazione è dopo il suo declarator e prima dell’inizializzatore.

In questo la x dichiarata internamente è inizializzata con il suo stesso valore (non definito).

Per la stessa ragione la visibilità di una variabile definita in un blocco esterno arriva fino al punto di dichiarazione della variabile che la nasconde, per esempio:

La variabile interna definisce un array di 10 elementi.
Vi faccio vedere due altri casi citati nel documento dello standard che trovo interessanti.

Il primo riguarda i membri di una classe che sono visibili dopo il loro punto di dichiarazione, anche se la classe è incompleta.

Il secondo, invece, riguarda i parametri template il cui punto di dichiarazione è dopo la loro completa definizione (inizializzazione compresa), per esempio:

Differenze tra compilatori.

Purtroppo nel mondo reale l’interpretazione dello standard non è così univoca come ogni programmatore vorrebbe. Per esempio il seguente codice:

Viene compilato tranquillamente dal mio Visual Studio 2012 (update 5), lo stesso avviene con il più recente 2015. Potete provare direttamente qui suo
webcompiler.

Mentre con un compilatore gcc (4.9.2) otteniamo il seguente errore di compilazione:

Potete provare qui su codechef

Alla prossima

mik

One Definition Rule (ODR)

Uno dei primi concetti a cui ci si imbatte leggendo lo standard è quello chiamato one definition rule. Cosa dice questa regola? In pratica afferma che in ogni translation unit non ci può essere più una definizione di una variabile, una funzione, di un tipo di classe, di un tipo enumerativo e di un template.
E’ possibile avere più dichiarazioni, ma è possibile avere solo una definizione.
Naturalmente, un programma potrà avere più definitizioni di un oggetto ma comunque potranno comparire solo una per translation unit, e tutte dovranno essere equivalenti. Se non è chiaro per “translation unit” intendo “unità di compilazione”, in parola povere un file .cpp.

Alcuni esempi

Esempio 1

Quello che proibisce la ODR.

Esempio 2

Ogni definizione dell’oggetto che si trova in diverse translation unit devono essere equilaventi, non come in questo caso.

Traslation unit 1

Traslation unit 2

Ulteriori info

  1. cppreference

Alla prossima

mik