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
Intel System Studio
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-2015. Alcuni diritti riservati. Testata giornalistica iscritta col n. 569 presso il Tribunale di Milano in data 14/10/2002. Pagina generata in 1.051 secondi.