Multithreading

Un processore single thread esegue un solo thread per processo

Un sistema multiprocessore classico esegue un solo thread per unità di calcolo

In informatica il multithreading indica il supporto hardware da parte di un processore di eseguire più thread. Questa tecnica si distingue da quella alla base dei sistemi multiprocessore per il fatto che i singoli thread condividono lo stesso spazio d'indirizzamento, la stessa cache e lo stesso translation lookaside buffer.

Il multithreading migliora le prestazioni dei programmi solamente quando questi sono stati sviluppati suddividendo il carico di lavoro su più thread che possono essere eseguiti in parallelo. Mentre i sistemi multiprocessore sono dotati di più unità di calcolo indipendenti per le quali l'esecuzione è effettivamente parallela, un sistema multithread invece è dotato di una singola unità di calcolo che si cerca di utilizzare al meglio eseguendo più thread nella stessa unità di calcolo. Le due tecniche sono complementari: a volte i sistemi multiprocessore implementano anche il multithreading per migliorare le prestazioni complessive del sistema.

Panoramica

Il paradigma del multithreading è diventato molto popolare verso la fine degli anni novanta quando le ricerche sull'incremento dell'instruction level parallelism si sono bloccate. Allora si è spostata l'attenzione dall'eseguire un singolo programma alla massima velocità all'occupare con la massima efficienza possibile le unità di calcolo. Si è appurato che molti programmi erano composti da più flussi paralleli o potevano essere scomposti in più thread paralleli con lievi modifiche al codice sorgente. Quindi migliorando l'esecuzione di thread paralleli si poteva migliorare l'esecuzione complessiva dei programmi. Questo ha spinto lo sviluppo dei sistemi multithreading e dei sistemi multiprocessore.

Questo filone di ricerca ha portato anche delle critiche, le principali sono:

• Più thread condividono le stesse risorse come cache o translation lookaside buffer e quindi possono interferire a vicenda rallentandosi.
• Le prestazioni dei singoli thread non migliorano, ma anzi possono degradare all'aumento dei thread concorrenti.
• Il supporto hardware del multithreading e dei sistemi multiprocessori richiede anche un contributo del software, i programmi e i sistemi operativi devono essere adattati per gestire questa nuova possibilità.

Clustered Multi-Thread

Il Clustered Multi-Thread è una tecnica che consente la progettazione di processori superscalari senza sacrificare tempo di ciclo, ma a costo di latenze di comunicazione maggiori.

Esempi

Uno dei maggiori esponenti di questa architettura sono i processori Bulldozer di AMD

Coarse-grained multithreading

Idea di base

Il multithreading coarse-grained (a grana grossa) prevede che il processore esegua un singolo thread fino a quando questo non viene bloccato da un evento che normalmente ha una elevata latenza (per esempio un cache miss), in questo caso il processore provvede a eseguire un altro thread che era pronto per l'esecuzione. Il thread di rimpiazzo rimane in esecuzione fino a quando il primo thread non è pronto per l'esecuzione.

Per esempio:

1. Ciclo i: l'istruzione j del thread A viene caricata
2. Ciclo i+1: l'istruzione j+1 del thread A viene caricata
3. Ciclo i+2: l'istruzione j+2 del thread A viene caricata, il caricamento provoca un cache miss con corrispondente richiesta nella memoria centrale
4. Ciclo i+3: il processore avvia l'esecuzione del thread B
5. Ciclo i+4: l'istruzione k del thread B viene caricata
6. Ciclo i+5: l'istruzione k+1 del thread B viene caricata

Concettualmente è una tecnica simile a quella presente nel multitasking cooperativo dei sistemi RTOS, in questi sistemi operativi quando un programma deve attendere un evento volontariamente cede la priorità a un altro programma pronto all'esecuzione.

Terminologia

Oltre che Coarse-grained multithreading viene definito Block o Cooperative multithreading.

Costo hardware

Il multithreading parte dal presupposto che il passaggio tra thread avvenga in modo rapido, questa tecnica effettua il passaggio in un ciclo di clock. Al fine di ottenere questo il processore deve replicare alcune componenti per i due thread come i registri interni, il program counter e alcuni registri di stato. Anche gli adattamenti a livello software sono relativamente modesti dato che il sistema operativo deve gestire un numero modesto di thread in esecuzione contemporanea.

Esempi

Molte famiglie di microcontrollori e di processori embedded implementano una gestione di più banchi di registri al fine di consentire un veloce context switch per la gestione degli interrupt. Questo può essere considerato un tipo multithreading.

• Intel Super-threading
• Intel Itanium 2

Fine-grained multithreading

Un sistema Fine-grained multithreading schedula più thread e ne esegue in contemporaneo le istruzioni al fine di occupare al meglio le unità d'elaborazione

Idea di base

Una tipologia di multithreading molto spinto prevede che il processore scambi il thread in esecuzione a ogni ciclo di clock.

Per esempio:

1. Ciclo i: l'istruzione j del thread A viene caricata
2. Ciclo i+1: l'istruzione k del thread B viene caricata
3. Ciclo i+2: l'istruzione h del thread C viene caricata

Questa tipologia di multithreading dovrebbe rimuovere la dipendenza dai dati dei singoli thread e quindi dovrebbe azzerare o comunque ridurre gli stalli della pipeline dovuta alla dipendenza dai dati. Dato che ogni thread dovrebbe funzionare in modo indipendente i singoli thread eseguiranno programmi non correlati e quindi vi saranno poche probabilità che le istruzioni di un thread necessitino dei risultati elaborati da un'istruzione di un altro thread in esecuzione in quel momento.

Concettualmente questa tecnica è simile al multitasking preemptive presente in molti sistemi operativi. Questa analogia parte dal presupposto che ogni slot di tempo dei programmi sia posto uguale a un ciclo di clock del processore.

Terminologia

Questa tecnica di multithreading inizialmente venne chiamata barrel processing ma attualmente la terminologia moderna definisce questa tecnica come pre-emptive o interleaved o time-sliced o fine-grained multithreading.

Costo hardware

In aggiunta alle componenti indicate precedentemente questa tecnica di multithreading richiede delle componenti aggiuntive che assegnino a ogni istruzione in esecuzione un'ID che permetta di identificare il thread proprietario. Questa tecnica richiede che lo scambio tra i thread avvenga senza cicli di clock di stallo e quindi richiede hardware più sofisticato; inoltre la presenza di molti thread in esecuzione in parallelo richiede generalmente cache e TLB più capienti al fine di poter servire i vari thread in modo efficiente.

Esempi

• Denelcor Heterogeneous Element Processor
• Sun Microsystems UltraSPARC T1
• Lexra NetVortex
• MIPS core 34K che implementa la Multi-Threaded ASE
• Raza Microelectronics Inc XLR

Simultaneous Multi-Threading

Un sistema Simultaneous Multi-Threading schedula più thread ma ne esegue uno solo per ciclo di clock

Idea di base

I moderni processori hanno più unità di calcolo che vengono utilizzate eseguendo le istruzioni dei singoli thread in parallelo. Gli attuali processori sono in grado di eseguire solamente poche istruzioni in parallelo di un singolo thread per via del ridotto parallelismo a livello di istruzioni che normalmente i thread possiedono. Quindi spesso alcune unità di elaborazione rimangono inutilizzate durante le elaborazioni. Per evitare questo il Simultaneous Multi-threading (SMT) esegue più thread in contemporanea e utilizza le istruzioni dei singoli thread per mantenere le unità di elaborazione sempre operative.

Per esempio:

1. Ciclo i: istruzione j e j+1 dal thread A, istruzione k dal thread B, tutte eseguite in simultanea
2. Ciclo i+1: istruzione j+2 dal thread A, istruzione k+1 dal thread B, istruzione m dal thread C, eseguite in simultanea
3. Ciclo i+2: istruzione j+3 dal thread A, istruzione m+1 e m+2 dal thread C, eseguite in simultanea.

Terminologia

Per distinguerlo dagli altri tipi di multithreading il termine temporal multithreading indica un tipo di multithreading che permette il completamento di istruzioni di un solo thread per ciclo di clock.

Costo hardware

In aggiunta all'hardware richiesto dal precedente tipo di multithreading, questa tecnica richiede che ogni stadio della pipeline tracci il thread d'appartenenza dell'istruzione e, dato che il processore ha più unità d'esecuzione, vi sono molte istruzioni da tracciare. Inoltre la cache e la TLB devono essere molto ampie per poter gestire un numero di thread così elevato dato che, eseguendo molte più istruzioni in parallelo, si fa un uso molto intenso delle risorse suddette.

Esempi

• DEC Alpha EV8 (non terminato)
• Intel Hyper-Threading
• IBM POWER5
• Power Processing Elements del processore Cell
• Sun Microsystems UltraSPARC T2

Ricerca

Attualmente la ricerca di settore si concentra su tecniche che permettano di scegliere rapidamente il thread da mandare in esecuzione in caso di stallo del thread in esecuzione. Un importante filone di ricerca è lo scheduler dei thread, che può essere gestito a livello hardware, a livello software o con un approccio misto.

Un'altra area di ricerca riguarda la tipologia di eventi che devono provocare uno scambio dei thread in esecuzione (cache miss, DMA, comunicazione inter thread, etc).

Se il multithreading replica tutti i registri visibili a livello software è possibile utilizzare il multithreading per implementare delle macchine virtuali. Ogni thread si troverebbe a gestire una propria macchina virtuale come se fosse eseguita da un processore separato e quindi potrebbe arrivare ad eseguire anche un intero sistema operativo indipendente.

Voci correlate

• Fork (programmazione)

Collegamenti esterni

• (EN) Denis Howe, multithreading, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• Lucidi sul multithreading (PDF), su di.unito.it (archiviato il 9 giugno 2006).
• Programmazione multi-thread, su Università di Napoli (archiviato il 23 aprile 2012).