Task-Based Design and Programming

Riuscire a determinare il numero ottimale di thread (cioè il numero di thread che massimizza sia la banda, sia l’efficienza relativa) è difficile.

Dalla strutturazione a livelli [Vanneschi07a] di un sistema di elaborazione, sappiamo come il livel- lo del sistema operativo, ed in particolare il nucleo, provveda alla gestione del processore nei con- fronti di attività concorrenti, fornendo al livello delle applicazioni l’astrazione dei processi e thread. Nel caso di un calcolatore convenzionale11_{, in realtà un singolo thread alla volta sarà in esecuzione}

all’interno del processore, nonostante questo non sia percepibile a livello applicativo (a meno di considerare eventuali ottimizzazioni architetturali come l’esecuzione superscalare, il pipelining, ed il multithreading). Nel caso di un processore multi-core, i thread logici sono mappati nei thread fi- sici, dove per thread fisici intendiamo la capacità elaborativa concorrente esibita dalla macchina hardware, così come astratta da parte della macchina assembler e firmware (in altre parole, nel con- testo dei processori multi-core, ad un thread fisico corrisponde un uno ed un solo core, sempre escludendo ottimizzazioni architetturali come l’esecuzione superscalare, il pipelining, ed il multith- reading), mentre i thread logici sono quelli forniti dal livello del sistema operativo.

Per computazioni che non richiedano primitive bloccanti (ossia operazioni che producano una commutazione di contesto), nella maggior parte dei casi l’efficienza è massima se è in esecuzione esattamente un thread logico per thread fisico.

Se non ci sono abbastanza thread logici in esecuzione per sfruttare tutti i core disponibili, si ha chia- ramente un sottosfruttamento delle capacità computazionali del processore, ed una conseguente

11 _{Cioè un sistema uniprocessore e nel quale in un qualsiasi istante non più di una istruzione macchina può essere in} fase di elaborazione.

inefficienza. Se al contrario ci sono più thread logici in esecuzione di quanti siano quelli fisici, pos- sono verificarsi overhead aggiuntivi, con un conseguente degrado della banda. Queste due situazio- ni opposte di inefficienza sono riferite in letteratura con i termini di undersubscription e oversubscription, rispettivamente.

Come introdotto sopra, la libreria Threading Building Blocks ha un runtime per la gestione dei task. Tale runtime è implementato dal task scheduler, che costituisce il cuore della TBB. Esso gestisce un pool di thread e nasconde la complessità dei thread nativi sottostanti.

La gestione del pool di thread operata dal task scheduler è tale da evitare il verificarsi di situazioni di undersubscription e oversubscription, selezionando il numero di thread logici che massimizza l’efficienza relativa. Esso mappa i thread logici in un modo tale da tollerare eventuali “interferenze” da parte di altri thread appartenenti allo stesso o ad altri processi.

Forme di parallelismo annidate rendono l’oversubscription probabile, dal momento che per una subroutine annidata non è semplice verificare se sta girando all’interno di un’operazione parallela ad un alto livello di annidamento. Anche la coordinazione della creazione di nuovi thread all’interno di thread indipendenti è un’attività complessa.

Per evitare la undersubscription è comunque importante prendere vantaggio del parallelismo a tutti i livelli di annidamento, senza rinunciare a decomporre il problema finché ha senso farlo. Sfortuna- tamente, trattando direttamente con thread crudi, questo non è per niente banale, rischiando per di più di finire facilmente in situazioni di oversubscription.

Quando si programma utilizzando i thread (logici), sorgono molte domande, come: come dovrebbe- ro essere suddivisi ed assegnati i task per tenere occupato ogni core del processore? Occorrerebbe creare un nuovo thread ogni volta che si ha un nuovo task, o sarebbe meglio creare e gestire un pool di thread? Il numero di thread dipende dal numero di core?

Queste sono domande cruciali per l’implementazione di un supporto al multitasking, e non dovreb- bero essere domande a cui un programmatore a livello applicativo dovrebbe rispondere.

TBB evita tutto questo fornendo al programmatore un supporto completo all’astrazione dei task: questo significa che è possibile ragionare in termini di task, piuttosto che di thread, e questo già in fase di progettazione. Il progetto potrà quindi considerare e prendere vantaggio di tutto il paralleli- smo riconoscibile nel particolare dominio applicativo di interesse, senza dover temere di incorrere in situazioni di oversubscription, dal momento che dietro le quinte il task scheduler di TBB eviterà tale fenomeno, assegnando opportunamente i vari task ai thread logici, ed allocando un thread logi- co per thread fisico di volta in volta disponibile, indipendentemente dal numero complessivo dei task.

Uno dei fattori chiave per il successo della TBB per quanto riguarda le performance, è che i task hanno un peso nettamente inferiore rispetto a quello dei thread: su sistemi Linux, iniziare e termina- re un task è circa 18 volte più veloce che iniziare e terminare un thread. Su sistemi Windows, tale rapporto va oltre le 100 unità. Questo è dovuto principalmente al fatto che un thread mantiene una sua copia di risorse private, come lo stato dei registri (tra cui il program counter) e lo stack delle chiamate di funzione. Tali risorse vanno allocate e deallocate ogniqualvolta un thread viene avviato e terminato, rispettivamente, e tale operazione ha un certo costo. Diversamente, un task, così come definito dalla TBB, è una semplice routine, e non può essere prelazionato a livello dei task dal runtime della TBB, sebbene il thread a cui il task è associato possa essere prelazionato dal sistema operativo, nel caso in cui quest’ultimo adotti uno schema di scheduling preemtive (con prelazione). Threading Building Blocks si prende cura dell’intera gestione dei thread, in modo tale che il pro- grammatore possa esprimere nel codice sorgente il parallelismo direttamente in termini di task.