Programmazione.it v6.4
Ciao, per farti riconoscere devi fare il login. Non ti sei ancora iscritto? Che aspetti, registrati adesso!
Info Pubblicità Collabora Autori Sottoscrizioni Preferiti Bozze Scheda personale Privacy Archivio Libri Corsi per principianti Forum
Intel Threading Building Blocks
Recensito da Paolo Raviola il 24-06-2008 ore 10:37
Copertina ISBN: 9780596514808
Autori: James Reinders
Editore: O'Reilly
Lingua: Inglese
Anno: 2007
Pagine: 332
Allegati: Nessuno
The Parallel Universe
La programmazione parallela esiste da molto tempo, ma solo negli ultimi anni, con l'avvento delle CPU multicore, ha raggiunto una maggiore diffusione, al di fuori del ristretto ambito dei supercomputer. Articoli divulgativi e ricerche teoriche si susseguono, e naturalmente i maggiori produttori di CPU multicore propongono strumenti di sviluppo per il proprio hardware, cercando di attirare i programmatori dalla loro parte. Il libro in esame si propone come il testo di riferimento di Intel per i suoi Threading Building Blocks (TBB).

Anzitutto nella primissima pagina, prima dell'elenco dei contenuti e dell'introduzione, troviamo un vero e proprio elogio della programmazione parallela, con testimonial di sicuro valore. L'affermazione più categorica è la prima, e proviene da Charles E. Leiserson, del MIT Computer Science and Artificial Intelligence Laboratory, che dice: "L'Era del Serial Computing è finita". Non gli è da meno Rudolf Eigenmann, della Purdue University, che, riferendosi alle architetture multicore, parla del "più grande sconvolgimento che la tecnologia dell'informazione abbia visto". Naturalmente il tempo è l'unico giudice per affermazioni così nette.

In una nota introduttiva Arch D. Robison, lead developer dei TBB, ricorda che non c'è un unico metodo per la programmazione parallela: sono stati proposti molti paradigmi, nuovi linguaggi, nuove estensioni ai linguaggi e librerie: TBB è, per l'appunto, una libreria. Egli fa poi una carrellata sulle soluzioni esistenti, che sono servite come base o fonte di ispirazione: POOMA, Chare Kernel (ora Charm++), Cilk, STAPL; dà un assaggio delle TBB parlando di lock e sincronizzazioni e chiude con il suo principio favorito: KISS (Keep It Simple, Stupid), applicato alla programmazione parallela.

Esiste l'apposito sito, dove si possono scaricare la libreria e le istruzioni per l'installazione. Per la comprensione del materiale non viene supposta nessuna conoscenza particolare sulla programmazione parallela, solamente una conoscenza (anche generica) dei C++ template come la Standard Template Library (STL). I primi due capitoli sono introduttivi; il primo vuole far capire a grandi linee la superiorità della soluzione TBB rispetto alle altre, il secondo tratta della programmazione parallela in generale. Dei capitoli successivi il terzo è fondamentale per imparare i TBB e per continuare la lettura con profitto. I capitoli dal quarto al nono si addentrano nei particolari, e il decimo riunisce le conoscenze così acquisite per usare nel miglior modo i TBB. Il capitolo 11 fornisce esempi e il capitolo 12 fa un po' di storia e si confronta con progetti analoghi.

Nel capitolo 1 si sottolinea il fatto che i TBB girano su qualunque processore, e su qualsivoglia sistema operativo con qualsiasi compilatore C++; inoltre sono scalabili: quando i core aumentano, non c'è bisogno di modificare al codice. Si evidenziano poi le caratteristiche rispetto agli altri package:
  • non si devono specificare thread, e quindi crearli, sincronizzarli e gestirli, ma task. Il compito fondamentale di mappare task e thread è svolto da TBB;
  • alcuni pacchetti consentono differenti tipi di threading, come eventi asincroni per le GUI; i TBB si concentrano sulla parallelizzazione di lavori computazionalmente intensi;
  • compatibilità con altri pacchetti: p.es., si possono mischiare direttive OpenMP e TBB;
  • l'enfasi è posta sulla scalabilità data-parallel: le performance aumentano se aumenta il numero di processori;
  • i TBB si basano sulla programmazione generica, p.es. STL.
I raw thread (come i POSIX thread o i Windows thread) o la Message Passing Interface (usata nell'ambiente dei supercomputer) esportano il controllo del parallelismo al suo livello più basso: sono, per così dire, i linguaggi assembly della programmazione parallela hanno il massimo grado di flessibilità, ma costano in termini di impegno di programmazione, debug e manutenzione. Il vantaggio dei task sui thread è enorme: alcuni esperimenti li danno ben 18 volte più veloci su macchine Linux e addirittura 100 volte su macchine Windows.

Il capitolo 2 serve di introduzione al parallelismo e giustamente si intitola Pensare parallelo. Nella programmazione seriale il primo pensiero è quello di selezionare il miglior algoritmo, o il linguaggio implementativo ritenuto più opportuno. Nella programmazione parallela si dovrebbe pensare come prima cosa al parallelismo intrinseco del lavoro da svolgere; questo dovrebbe poi portare alla scelta degli algoritmi e dell'implementazione. Gli elementi del "pensare parallelo" possono essere così classificati: decomposition, scaling, thread, correctness, abstraction and pattern, Cache, Intuition. Vediamone alcuni brevemente:
  • Decomposition significa decomposizione del problema in sotto-problemi. Al più alto livello, il parallelismo esiste nella forma di dati, sui quali operare in parallelo o nella forma di task che girano in concorrenza; i due procedimenti non sono mutuamente esclusivi. Un semplice esempio del primo caso è trasformare un certo insieme di lettere da minuscole a maiuscole: lo stesso task opera su dati diversi. Un altro esempio, relativo al secondo metodo, è un insieme di numeri, sui quali si deve fare la media, trovare il minimo, il massimo, eseguire un OR binario, ecc.: task diversi che operano sugli stessi dati. Un terzo esempio, che condurrà poi a una soluzione mista, è la spedizione in massa di lettere. Ciascuna persona può avere un compito ben preciso: scrivere l'indirizzo, mettere il francobollo, ecc. (parallelismo fine-grained), oppure la singola persona (in parallelo con tutte le altre) esegue l'intero lavoro (parallelismo coarse-grained). Ad un certo punto, si scopre che scrivere gli indirizzi è il task più oneroso e quindi si allocano 3 persone. Questo è proprio quello che fanno i TBB: l'utente fornisce dati e specifica i task e poi lascia che i TBB decidano come allocare risorse.
  • Scaling and Speedup:possiamo dire che il programma non è più scalabile quando l'aggiunta di nuovi core non aumenta la velocità di elaborazione, o addirittura la fa diminuire. Per risolvere questo problema la libreria TBB ha il grain size, un concetto che verrà sviluppato nei capitoli 3 e 4. A proposito di scalabilità e prestazioni si può citare la Amdahl's Law, che in sostanza dice: un programma non può andare più veloce delle sue parti che non vanno in parallelo. Questo fatto sembrerebbe limitare molto l'incremento prestazionale dell'elaborazione parallela rispetto a quella seriale. Ma John Gustafson, due decenni dopo, suggerì un riesame della legge di Amdahl: man mano che aumenta il carico di lavoro la parte parallelizzabile aumenta, e quindi le prestazioni aumentano. Le osservazioni di Amdahl e Gustafson sono entrambe giuste, ma la seconda prevede un mondo in evoluzione, mentre la prima è valida in un ambiente statico, quando, per esempio, facciamo girare una singola applicazione con il solito benchmark. La conclusione è questa: non ci sono programmi che vanno bene sia in single core che in multicore; molto raramente il miglior algoritmo seriale è anche il miglior algoritmo parallelo, e viceversa.
  • Mutual Exclusion and Locks: la soluzione senz'altro migliore è quella di decomporre il problema in modo che la sincronizzazione sia implicita, ed evitare quella esplicita, che porta sempre a degradi prestazionali.
  • Correctness: l'ordine di esecuzione dei thread di un programma cambia di volta in volta (i programmi multithread sono non deterministici), bisogna assicurarsi che il risultato sia sempre il medesimo. A questo proposito può essere di aiuto l'Intel Thread Checker.
  • Pattern: un libro fondamentale nella programmazione seriale è Design Patterns: Elements of Reusable Object-Oriented Software (Addison Wesley). Analogo per la computazione parallela è Patterns for Parallel Programming, di Mattson et al. (Addison Wesley). Mattson suggerisce quattro spazi di progetto per passare dalle prime intuizioni a un programma parallelo: Finding concurrency, Algorithm structures, Supporting structures, e Implementation mechanisms. L'esempio della spedizione in massa di posta fatto in precedenza può essere tradotto in codice usando questi quattro spazi di progetto.
Come già detto, il capitolo 3 (Algoritmi di base) è fondamentale per la comprensione dei TBB; si introdurranno i concetti di recursione, task stealing, e di algorithm template. TBB offre i seguenti algoritmi generici paralleli: parallel_for, parallel_reduce e parallel_scan. Un esempio di Quicksort (descritto nel capitolo 11) sarà implementato usando il parallel_for in maniera recursiva. Decomporre un problema in maniera recursiva è molto meglio della ovvia divisione statica del lavoro e si adatta molto bene al task stealing piuttosto che una coda globale di task. Per la soluzione di un problema si impiegano di solito più tecniche, p.es. un parallel_for, che controlla un insieme parallelo di pipeline; TBB facilita molto l'implementazione di questi mix. Nella sezione Initializing and Terminating the Library abbiamo finalmente il primo esempio di codice: qualunque thread che usi un template di algoritmo o il task scheduler deve avere un oggetto tbb :: task_scheduler_init. Vediamo un esempio di inizializzazione della libreria:
  1. <span style="font-size:1.0em">#include "tbb/task_scheduler_init.h"
  2. using namespace tbb;
  3.  
  4. int main( ) {
  5.   task_scheduler_init init;
  6.    ...
  7.   return 0;
  8. }</span>


Il costruttore di task_scheduler_init ha un parametro opzionale, che specifica il numero desiderato di thread e può essere uno dei seguenti:
  • task_scheduler_init :: automatic, il default quando il parametro non è specificato;
  • task_scheduler_init :: deferred, che rimanda l'inizializzazione fino a quando il metodo task_scheduler_init :: initialize(n) non è chiamato;
  • un intero positivo.
Usare questo parametro è utile nello sviluppo del codice; in fase di produzione, è meglio omettere il parametro o usare task_scheduler_init::automatic, cioè è meglio posporre la decisione a runtime. Va notato che il task scheduler prende tempo per partire e per fermarsi, quindi è bene usarlo con parsimonia.

Vediamo il parallel_for: supponiamo di voler applicare la funzione Foo a ciascun elemento di un array. La versione seriale di questa procedura è la seguente:
  1. <span style="font-size:1.0em">void SerialApplyFoo( float a[], size_t n ) {
  2.   for( size_t i=0; i< n; ++i )
  3.     Foo(a[ i ]);
  4. }</span>


Lo spazio delle iterazioni è di tipo size_t e va da 0 a n-1. Il template tbb :: parallel_for suddivide questo spazio in blocchi e fa girare ciascun blocco in un thread separato. Il primo passo è convertire il corpo del loop in una forma che operi su blocchi. La forma è un oggetto nello stile STL, chiamato oggetto body, nel quale operator() elabora un blocco. Vediamo il codice:
  1. <span style="font-size:1.0em">#include "tbb/blocked_range.h"
  2. class ApplyFoo {
  3.   float *const my_a;
  4. public:
  5.   void operator( )( const blocked_range< size_t >& r ) const {
  6.     float *a = my_a;
  7.     for( size_t i=r.begin(); i!=r.end( ); ++i )
  8.       Foo(a[ i ]);
  9.   }
  10.   ApplyFoo( float a[] ) :
  11.     my_a(a)
  12.   {}
  13. };</span>


Notare l'argomento di operator: un blocked_range< T > è una classe fornita dalla libreria: descrive uno spazio delle iterazioni a una dimensione sul tipo T. Ed ecco la versione parallela:
  1. <span style="font-size:1.0em">void ParallelApplyFoo( float a[ ], size_t n ) {
  2. parallel_for(blocked_range< size_t >(0,n,YouPickAGrainSize), ApplyFoo(a) );
  3. }</span>


Il grain size è un parametro molto importante: se si allocano troppi thread per un certo lavoro, si spenderà troppo tempo nelle sincronizzazioni, cioè si avrà un overhead alto; se i thread sono troppo pochi, non si sfrutterà a fondo la parallelizzazione. Per un particolare problema, si può procedere a tentativi, oppure lasciare la gestione ai TBB con l'automatic grain size.

Vediamo ora la parallel_reduce. Applicare una funzione come sum, max, min o un logical AND su tutti i membri di un gruppo significa effettuare una reduction operation. Lo schema esemplificativo adottato è lo stesso del parallel_for: esempio seriale di SerialSumFoo, costruzione di una classe, esempio finale di ParallelSumFoo. Un esempio più complesso cerca l'indice del più piccolo elemento di un array. Gli spazi di iterazione più complessi del blocked_range< T > devono essere suddivisi in sottospazi con uno splitting constructor. Per illustrare questo concetto si fa l'esempio di un range a due dimensioni: blocked_range2d.

La funzione parallel_scan calcola un parallel prefix della forma y[ i ] = y[ i-1 ] op x[ i ]. Ad esempio, se op è l'operazione di addizione, il parallel prefix diventa una somma. Nell'esempio proposto, si vede che la parallel_scan fa più lavoro della versione seriale, ma riesce a distribuirlo fra thread hardware e quindi a essere più veloce.

Il capitolo si chiude con le Recursive Range Specification, dove vengono spiegati gli splitting constructor e gli splittable range. Inoltre si dà una definizione più formale del grain size: un range è ricursivamente suddivisibile fino a quando un'ulteriore suddivisione porterebbe a prestazioni peggiori di quelle che si avrebbero in esecuzione seriale.

Il capitolo 4 tratta del supporto offerto da TBB ad altri algoritmi generici paralleli più complessi di quelli del capitolo 3 e usati meno comunemente. Questi includono i Parallel Algorithms for Streams, che comprendono il parallel_while e il pipeline, e i Parallel sort, che comprendono il parallel_sort. In particolare, quest'ultimo si propone di ridurre le tempistiche, rendendole proporzionali a O(n), mentre la versione seriale è proporzionale a O(n log n). Per alcuni loop, il numero di iterazioni non è noto a priori, oppure il corpo del loop può aggiungere iterazioni prima che il esso finisca: a questo serve il parallel_while; una linked list è invece un esempio di spazio di iterazione non noto a priori. Come nel capitolo precedente, viene presentato un esempio di codice seriale SerialApplyFooToList, che processa una linked list e poi il codice parallelo ParallelApplyFooToList e si discute sulla scalabilità dell'approccio adottato.

Nel paragrafo dedicato alla pipeline passiamo al campo del video processing e consideriamo quelle operazioni sui frame video indipendenti uno dall'altro e che quindi possono essere eseguiti in parallelo. Un altro esempio è il seguente: lettura di un file di testo, rendere maiuscola la prima lettera di ciascuna parola e scrivere il risultato in un nuovo file di testo. Il template pipeline supporta solo pipeline lineari, ma può essere usato anche per pipeline non lineari, modificando opportunamente il problema; un esempio di pipeline non lineare è questo: i processi A e B inviano l'output al processo C, che invia due output ai processi D e E. Viene infine descritta dettagliatamente la classe parallel_sort, che crea dei subtask che possono girare in parallelo, e si conclude con l'illustrazione del suo funzionamento con due esempi.

Il capitolo 5 descrive i Container di TBB, che permettono a thread multipli di invocare un metodo del container in contemporanea. Per quanto possibile, l'interfaccia è simile a quella di STL, con alcune piccole differenze. I TBB container forniscono dei meccanismi di finegrained locking e di lock-free; il primo provvede a bloccare solamente le porzioni di codice, che realmente necessitano di essere bloccate, il secondo è penalizzato da qualche attesa alla fine dei calcoli, ma il codice gira senza bisogno di lock espliciti. I TBB container non hanno un allocator argument; la libreria gestisce il controllo dell'allocazione di memoria. La classe concurrent_queue implementa una coda concorrente; thread multipli possono fare in contemporanea push e pop dalla coda. La coda è un FIFO, ma in ambiente concorrente la definizione di first diviene problematica. La sola garanzia di ordine offerta da concurrent_queue è che se un thread fa il push di valori multipli e un altro thread fa il pop di questi stessi valori, i valori estratti manterranno l'ordine in cui sono stati inseriti. Enteressante notare che concurrent_queue :: size( ) è definita come il numero di operazioni di push meno il numero di operazioni di pop, e quindi il valore può anche diventare negativo. L'operazione di push è fornita dal metodo push, mentre quella di pop è implementata con due metodi: pop_if_present, non bloccante, e pop, bloccante. Per definizione concurrent_queue non ha limiti, se non la disponibilità fisica di memoria. Le code sono molto usate nella programmazione parallela nel problema di produttori e consumatori; per ragioni di efficienza, si dovrebbe però prima pensare a parallel_while o pipeline, perché queste mantengono la località dei riferimenti.

Il concurrent_vector è un array di dimensioni variabili, ai cui elementi si può accedere in contemporanea mentre questo sta cambiando dimensioni. Per garantire la concorrenza e per evitare problemi di accesso in contemporanea, vengono usati i due metodi grow_by e grow_to_at_least; concurrent_vector ha più overhead di std :: vector e va quindi usato solo in caso di vera necessità.

La concurrent_hash_map è una hash table, che permette accessi concorrenti. La tabella è una mappa tra una chiave e un tipo T. Viene proposto un semplice esempio: una hash table che mappa stringhe in interi. Una concurrent_hash_map agisce come un contenitore di elementi del tipo std :: pair< const Key,T >. Per scrivere e leggere la tabella ci sono le classi accessor e const_accessor, che è bene usare con parsimonia, poiché possono bloccare i thread in accesso.

Nel capitolo 6 viene descritta la gestione dell'allocazione di memoria mediante allocatori scalabili; il capitolo spiega come utilizzare quelli dei TBB. La sezione Limitations si apre — onestamente — con la descrizione di alcune limitazioni: nel range da 9K a 12K c'è uno spreco di spazio e inoltre la gestione del paging non è molto sofisticata. L'allocazione di memoria è un argomento separato dai TBB, ma è un compito importante e delicato, soprattutto in ambiente multithread. Quando vengono usati allocatori nonthreaded in ambienti multithread, le prestazioni, per problemi di contesa, possono diminuire all'aumentare dei processori.
Un altro problema è il false sharing: il processore accede alla main memory e tiene in cache i dati. L'accesso a ogni linea di questa cache dovrebbe essere fatto dallo stesso thread, altrimenti si assiste a un continuo avanti e indietro tra cache e main memory, che penalizza le prestazioni. I Memory Allocator di TBB offrono due scelte: scalable_allocator e cache_aligned_allocator. Il primo consente la scalabilità, ma non protegge completamente dal false sharing; il secondo è scalabile ed evita il false sharing, ma, allocando a blocchi multipli della cache line (tipicamente 128 byte) può generare spreco di memoria; bisognerebbe usarla se il false sharing è un problema e dopo aver fatto alcuni test. Bisognerebbe comunque accertarsi che tutte le allocazioni di memoria non causino problemi, anche quelle fatte al di fuori del TBB.
Vi sono poi delle funzioni, come scalable_malloc, che possono rimpiazzare le equivalenti di STL; in alcuni casi però, scalable_malloc o scalable_free fanno semplicemente delle chiamate a malloc e free. Il codice per rimpiazzare new e delete si trova nel capitolo 11.

In alcuni casi i sincronismi espliciti sono ancora necessari; è ciò che viene spiegato nel capitolo 7. La mutual exclusion dei task porta come conseguenza alla programmazione thread-safe, visto che TBB mappa i task in thread. Il consiglio è di usare una granularità fine, in modo da bloccare solo la porzione di codice strettamente necessaria. Le operazioni di read non modificano il contenuto e quindi sono thread-safe, ma ci sono due esempi che contraddicono questa affermazione: oggetti con uno stato interno e oggetti che modificano il proprio stato quando vengono usati, come una struttura self-balancing binary search tree. I TBB offrono due tipi di mutual exclusion: Mutexes e Atomic operations:list][*]Mutexes: un mutex è una variabile globale a cui più task possono accedere; i task devono richiedere un lock sul mutex, prima di eseguire codice che non vogliono sia eseguito in concorrenza. Un semplice esempio è fornito dall'allocazione di un nodo in una lista di nodi. Vi sono diversi tipi di mutex; il più semplice è lo spin_mutex, ma esistono anche i queuing_mutex, gli spin_rw_mutex, e i queuing_rw_mutex. Nei sistemi Windows un mutex è una CRITICAL_SECTION, in Linux è un pthread mutex. Vengono infine descritte le Patologie dei Lock: il ben noto Deadlock, il Convoying e il priority inversion. Viene descritta l'implementazione in C++ di un mutex, che in pratica è un wrapper delle chiamate di sistema.
[*]Nella sezione delle Atomic Operations si descrive l'implementazione C++ delle operazioni atomiche e le situazioni in cui è meglio usare queste ultime invece della mutua esclusione. Vengono illustrati appositi operatori di overload, che implementano le operazioni atomiche. Inoltre si trova un interessante box del problema A-B-A sulle liste linkate; il problema sorge quando un thread testa una locazione di memoria per assicurarsi che il valore sia A, e procede con un aggiornamento solo se il valore è A. Si trova poi una discussione sulle Memory Consistency and Fences. Un processore può riordinare le letture e le scritture in memoria in un modo che non è più consistente con l'ordine originale. Alcune architetture, come Intel Itanium, IBM POWER, PowerPC, e i processori Alpha hanno una consistenza debole, per migliorare le prestazioni. Per i processori SPARC tutto dipende dal sistema operativo: Solaris usa il TSO (totalstore order) e Linux usa l'RMO (relaxed-memory order). Quindi SPARC ha una debole consistenza sotto Linux, ma non sotto Solaris. La materia è complessa, ma se si programma con IA-32 o Intel 64/AMD64 è bene sapere che il modello usato su queste piattaforme possiede la più forte consistenza in assoluto. Le fence sono invocate per impedire la riorganizzazione delle istruzioni.
[/list]Nel Capitolo 8 viene descritto un metodo thread-safe per calcolare il tempo trascorso, implementato dalla classe tick_count; tick_count :: now funziona anche se gira su core diversi. Il valore di tick_count :: now è un valore che rappresenta il tempo corrente assoluto; ha significato solo se confrontato con altri di tipo tick_count. La risoluzione di tick_count corrisponde alla massima risoluzione possibile offerta dalla piattaforma hardware su cui sta girando.

Nel capitolo 9 viene descritto il task scheduler, che è il cuore dei TBB; solitamente però non viene utilizzato direttamente. È meglio usare i template high-level descritti nei capitoli precedenti, ma il suo utilizzo è appropriato per esigenze particolari, come ad esempio algoritmi high-performance con task non sospensivi. Questo capitolo è destinato a chi vuole approfondire la materia, ma non è strettamente necessario per l'uso dei TBB. Il task scheduler gestisce un pool di thread e nasconde la complessità dei thread nativi; inoltre gestisce bene le questioni qui sotto elencate.
  • [Oversubscription: i logical thread si mappano sui physical thread dell'hardware; se si prevede di non bloccarsi su operazioni di I/O, la massima efficienza si raggiunge quando per ogni logical thread c'è un physical thread. Se non si riesce a occupare tutti i thread fisici, c'è inefficienza, al contrario invece c'è oversubscription e in definitiva overhead. Il task è tipicamente una piccola routine, sulla quale lo scheduler non ha diritto di prelazione (ma naturalmente può agire sul logical thread associato a quel task).
  • Fair Scheduling: i sistemi operativi general purpose distribuiscono le fette di tempo con uno schema round-robin, e questo è il metodo più onesto (fair) di allocare la risorsa tempo senza conoscere la struttura ad alto livello del programma. Il task scheduler possiede informazioni non disponibili al S.O. e può così favorire l'efficienza a scapito della fairness.
  • High Coding Overhead: come già detto, i raw thread, come i pthread di POSIX o i Windows thread, offrono il controllo del parallelismo al suo più basso livello, ma la programmazione diventa difficile e poco intuitiva e il codice dipende molto dal S.O.
  • Load Imbalance: il task scheduler cerca di assegnare il lavoro ai thread in modo equo, dividendolo in modo continuativo e recursivo, se necessario. Questo è garanzia di scalabilità, poiché non si deve riscrivere un applicativo quando aumenta il numero di core a disposizione.
  • Portability: tutti i compilatori C++ conformi allo standard funzionano con i TBB. La prima versione di TBB funzionava su Windows, Linux e Mac OS X per i processori a 32 bit e per il 64-bit Itanium,e con compilatori Intel, Microsoft e GNU. In seguito è poi stato aggiunto il supporto per Intel 64 e AMD64.
Viene presentato un esempio di uso diretto del task scheduler per il calcolo della successione di Fibonacci. Come al solito, viene visto prima l'algoritmo seriale recursivo, poi quello parallelo. Bisogna notare che il mappaggio dei task in thread fisici è di tipo non-preemptive. Ciascun thread ha un metodo execute(), durante l'esecuzione del quale il task è legato al thread. Il parallelismo è generato tipicamente da un'operazione split/join: il task padre forka due figli e specifica un task di continuation. Un secondo modello di parallelismo è il blocking style, che usa una continuation implicita. In questo caso il task parent si blocca fino al completamento dei figli, soluzione più semplice da programmare, ma meno efficiente.

Il task scheduler valuta un grafo dei task. I nodi del grafo sono task, e ciascuno punta al suo genitore; l'esecuzione può essere depth-first o breadth-first; l'autore apre una discussione su pregi e difetti. In definitiva, la strategia fondamentale è una breadth-first theft and depth-first work.

Si descrivono poi tecniche utili allo scheduling dei task: Recursive Chain Reaction, Continuation Passing, con un esempio della successione di Fibonacci, Scheduler bypass, dove si può specificare direttamente il prossimo task da eseguire, Recycling, dove si può specificare l'allocazione e la deallocazione dei task e Lazy copying, quando può essere utile copiare una struttura dati solo quando un altro thread ruba il task.

Il task scheduler utilizza il task stealing. La tecnica di schedulazione è simile a quella di Cilk, un progetto di ricerca. Vi è una dettagliata descrizione di classi e del loro funzionamento, per le quali si rimanda al libro. Il task scheduler lavora in maniera efficiente per il parallelismo fork-join con molte fork in modo che il task stealing possa avere un comportamento breadth-first. Il task scheduler non è il più semplice possibile, perché è progettato per l'efficienza e la velocità.

Il Capitolo 10 fornisce informazioni non strettamente necessarie alla programmazione TBB; sono comunque argomenti importanti che bisognerebbe conoscere: debugging, efficienza dell'implementazione e compatibilità con altri pacchetti. Vengono descritti i 5 punti base usati da Intel per l'efficiente costruzione di un programma parallelo:
  1. Think Parallel;
  2. Relaxed sequential execution;
  3. Ove possibile: a) uso degli algorithm template (capitoli 3 e 4) invece dei raw task; b) algorithm template invece dei lock; c) scalable memory allocator (quindi non malloc o new);
  4. debug: debuggare prima la versione seriale; provare poi due thread, poi quattro, e così via; usare Intel Thread Checker;
  5. Usare l'Intel Thread Profiler per fare tuning.
E arriviamo così alla spiegazione di cosa si intenda per relaxed sequential execution. La maggior parte dei programmi paralleli possono girare benissimo in seriale, ma alcuni necessitano di girare in parallelo. Un esempio di problema produttore/consumatore può servire a illustrare quanto detto: un contenitore di due unità e due programmi che operano, rispettivamente, delle PUT PUT PUT e GET GET GET (in triplette non scindibili); chiaramente bisogna fare un interleaving, cioè una concorrenza. Dato che i programmi paralleli sono più difficili da debuggare, TBB assume che il programma sia corretto se eseguito in seriale. Qui entra in gioco il modello di relaxed sequential execution: la parola relaxed si riferisce alla nozione che i programmi seriali sono limitati da dipendenze seriali implicite (come il program counter) e che le librerie concorrenti introducono il maggior grado di parallelismo possibile senza pregiudicare l'esecuzione sequenziale. Il consiglio finale è di progettare programmi che non richiedano forzatamente l'esecuzione in parallelo. Si raccomanda di usare librerie solamente thread-safe nelle applicazioni TBB, altrimenti il risultato è indefinito; in ambiente Windows si è protetti già a livello di compilatore, che genera un errore quando non si usano librerie thread-safe. La regola per avere programmi thread-safe con librerie non thread-safe è semplice: non invocare metodi o funzioni in parallelo sullo stesso oggetto. I concurrent container sono più permissivi e consentono l'esecuzione in parallelo sullo stesso oggetto container.

Per il codice di release è bene seguire queste regole:
  • non specificare il numero di thread nella task_scheduler_init, lasciare il settaggio in automatico.
  • Lasciare la TBB_DO_ASSERT indefinita o settata a 0.
  • Lasciare la macro TBB_DO_THREADING_TOOLS indefinita o settata a 0.
Per la macro TBB_DO_THREADING_TOOLS è disponibile documentazione; la macro serve per l'Intel Thread Profiler e l'Intel Thread Checker. Quest'ultimo traccia i messaggi di sincronizzazione di ciascun thread. Non ci sono speciali precauzioni da prendere nell'usare altri pacchetti, solamente bisogna prestare attenzione all'utilizzo del task scheduler. OpenMP (di cui si è parlato nel capitolo 1) può essere usato tranquillamente.

Nel Capitolo 11, dopo le parti didattiche e teoriche dei capitoli precedenti, vediamo finalmente qualche esempio concreto. La lettura del libro potrebbe anche iniziare da questo capitolo, per rendersi conto delle potenzialità di TBB, rimandando a dopo l'approfondimento analitico. I primi esempi intendono mettere l'utente a suo agio con TBB, mostrando alcune operazioni elementari. Seguono esempi un po' più complessi; gli ultimi esempi sono specialistici e riguardano i giochi e il processamento dei pacchetti; tutto il codice sorgente degli esempi può essere scaricato.

Lo studio di questi esempi dovrebbe chiarire gli aspetti più ardui della trattazione precedente e portare il lettore alla classica esclamazione di "Aha!". Ci sono poi altri esempi non così emblematici, ma che comunque contribuiscono alla ulteriore comprensione dei TBB. I primi due esempi sono abbastanza simili: il primo esegue una media sui valori in input e il secondo simula una propagazione di onde; entrambi usano il parallel_for e il secondo anche il blocked_range. Il terzo esempio propone una moltiplicazione di matrici e usa il blocked_range2d. Il quarto esempio esegue un merge di due sequenze ordinate e richiede un po' di familiarità con STL. Il quinto esempio serve a trovare sottostringhe all'interno di una stringa più grande e propone considerazioni sul grain size, applicato a una stringa di Fibonacci (per la cui definizione si rimanda al libro); si raggiunge un incremento di velocità di 1.9, vicino al limite teorico di 2.

Un intero paragrafo è poi dedicato a The Game of Life, inventato dal matematico John Horton Conway e reso popolare da Martin Gardner, sulle colonne di Scientific American. L'esempio proposto usa del managed code per l'interfaccia utente e il parallel_for per l'elaborazione. TBB decide a runtime quanti task creare, in modo da ottimizzare lo sfruttamento dell'hardware. Gli esempi successivi riguardano il parallel_reduce: il primo è una semplice somma di valori in un array, mentre il secondo è una versione parallela del crivello di Eratostene, per la ricerca dei numeri primi; l'esempio dimostra, in particolare, l'utilizzo del lazy splitting. Il successivo esempio è dedicato alle concurrent_hash_map: si vogliono contare le occorrenze di stringhe in un array. Si parte da un'implementazione seriale e, passo passo, si arriva al codice parallelo; molto interessante notare che, se si fossero usati i mutex nativi di Win32, oppure la CRITICAL_SECTION, le prestazioni sarebbero addirittura peggiorate, rispetto al codice seriale. Usando invece concurrent_hash_map si ottiene un incremento delle prestazioni del 125% (con 2 thread) e del 150% (con 4 thread). L'esempio successivo riguarda il Quicksort, e viene illustrato il task stealing e il range splitting; vi sono pochi commenti, ma codice e figure illustrano bene il comportamento dell'algoritmo.

E arriviamo a un esempio di uso diretto del task scheduler: si tratta dell'algoritmo di Strassen, usato nella moltiplicazione di matrici. In un sistema quad core, per una matrice 1024x1024 si ha un incremento di 2.34 volte, senza particolari espedienti di implementazione. I successivi esempi illustrano tecniche avanzate di programmazione dei task, come la creazione di un task "fratello" del main, allo stesso livello, o la creazione di una pipeline con una fork, per evitare i lock attraverso la sincronizzazione implicita. Venngono illustrati alcuni risultati provenienti da una macchina dual core su cui gira Windows Vista.

Il successivo esempio è molto interessante: si tratta di usare le pipeline (capitolo 4) e una concurrent hash map (capitolo 5) per implementare la gestione di pacchetti, per esempio all'interno di un router. Dato che la gestione solitamente avviene su device speciali, questo esempio dimostra come TBB può aiutare la progettazione di software per i sistemi embedded multicore. L'esempio mostra una piccola rete locale, che usa un protocollo FTP per il trasferimento dei dati. La pipeline dell'esempio simula tre passi: Network address translation (NAT), Application Layer Gateway (ALG) e Packet forwarding. Anche in questo caso è disponibile il codice completo e per la terminologia e i concetti NAT si rimanda alla documentazione ufficiale.

I successivi due esempi riguardano l'allocazione di memoria: il primo riguarda il rimpiazzo di new e delete, il secondo quello di malloc. Seguono gli esempi più complessi tra quelli proposti; vediamoli brevemente. Il primo riguarda l'implementazione delle componenti fondamentali di un gioco, e usa direttamente il task scheduler. Solitamente i giochi vengono decomposti nelle parti di rendering, di calcolo delle leggi fisiche (p.es. la forza di gravità), e così via. Di solito si alternano fasi di alto parallelismo seguite da fasi seriali; vi è una descrizione dettagliata delle scelte implementative, un giudizio sull'overhead e il codice completo. Come esempio finale, esaminiamo l'Open Dynamics Engine, un motore di calcolo per le interazioni fisiche, che ha due componenti principali: la simulazione della dinamica di un corpo rigido e un motore di rilevamento delle collisioni. Il fatto che il numero degli oggetti in gioco cambi, rende la soluzione con parallel_for non ottimale, mentre il task scheduler dà la possibilità di creare nuovi task in modo dinamico.

Nel Capitolo 12 si parla di alcune fonti dalle quali si è tratta l'ispirazione per certe caratteritiche dei TBB. Una lista di articoli e libri alla fine del capitolo fornisce proposte per ulteriori letture. Il capitolo contiene anche una breve spiegazione delle funzioni lambda, il cui inserimento nel C++ è fortemente voluto da Arch Robison, progettista capo dei TBB. La storia di TBB si basa su quattro assunzioni chiave:
  • supporto per i generici programmi C++ con i compilatori esistenti;
  • esecuzione relaxed sequential (capitolo 10);
  • uso del parallelismo ricursivo e di algoritmi generici;
  • uso del task stealing.
Si trovano poi alcune sezioni riguardanti argomenti specifici. Il primo è il generic programming: si può dar credito alle STL di Alexander Stepanov per aver reso popolare questo stile; la separazione tra algoritmi e container è l'idea basilare. TBB utilizza gli stessi principi, ma lo fa attraverso recursive ranges e non iterators. Il generic programming è supportato in C++ attraverso l'uso dei template, che forniscono un livello di astrazione mantenendo nel contempo l'opportunità per prestazioni ottimali.

I TBB sono stati progettati avendo in mente le cache e quindi cercando di limitare i movimenti di dati da/verso la main memory. Nell'esempio del Quicksort (capitolo 11) viene esplicitato il massimo parallelismo attraverso il concetto di cache. E infine una semplice formulazione concreta di lambda function: un programmatore C++ può scrivere il corpo di un loop in-place, invece di scrivere una funzione nello stile STL. Una capacità simile si trova nei metodi anonimi del C#, nelle classi inner di Java, e nelle lambda expression del LISP.
proIl testo in esame è senz'altro il più completo sull'argomento trattato e l'esperienza dell'autore in questo campo è fuori discussione. Oltre a una trattazione teorica della materia, vi sono molti esempi, dai più semplici a quelli più complessi, che coinvolgono anche problematiche reali. In conclusione un libro da leggere attentamente e da consultare continuamente per chi vuole cimentarsi nel campo della programmazione parallela.
controForse gioverebbe al libro, in alcuni casi, una più precisa catalogazione degli argomenti all'interno di ciascun capitolo. Per esempio, nel capitolo 7 vi sono due paragrafi con lo stesso nome; dato che la materia è difficile, bisognerebbe cercare una suddivisione più particolareggiata, anche adottando una numerazione per l'ulteriore suddivisione dei sottoparagrafi.
Precedente: L'interfaccia audio con le API (4/5)
Successiva: A volte ritornano: gli applet Java (2/2)
Copyright Programmazione.it™ 1999-2014. Alcuni diritti riservati. Testata giornalistica iscritta col n. 569 presso il Tribunale di Milano in data 14/10/2002. Pagina generata in 0.422 secondi.