Multithreading
Il multithearding in informatica 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. I sistemi multiprocessore sono dotati di più unità di calcolo indipendenti, un sistema multithread invece è dotato di una singola unità di calcolo che si cerca di utilizzare al meglio eseguendo più theard nella stessa unità di calcolo. Le tecniche sono complementari, a volte i sistemi multiprocessore implementano anche il multithreading per migliorare le prestaaioni complessive del sistema.
Panoramica
Il paradigma del multithearding è 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ù thread paralleli o potevano essere scomposti in più thread paralleli con lievi modifiche al codice sorgente. Quindi miglioranddo l'esecuzione di theard parappeli 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ù theard 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 multithearding e dei sistemi multiprocessori richiede anche un contributo del software, i programmi e i sistemi operativi devono essere adattati per gestire questa nuova possibilità
Coarse-grained multithreading
Idea 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 esecuzioni fino a quando il primo thread non è pronto per l'esecuzione.
Per esempio:
- Ciclo i : l'istruzione j del thread A viene caricata
- Ciclo i+1 : l'istruzione j+1 del thread A viene caricata
- Ciclo i+2 : l'istruzione j+2 del thread A viene caricata, il caricamento provoca un cache miss con corrispondente richiesta nella memoria centrale
- Ciclo i+3 : il processore avvia l'esecuzione del thread B
- Ciclo i+4 : l'istruzione k del thread B viene caricata
- 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 or 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 interrupr. Questo può essere considerato un tipo multithreading.
- Intel Super-threading
- Intel Itanium 2
Fine-grained multithreading
See article: barrel processor
Idea di base
Una tipologia di mutithreading molti spinto prevede che il processore scambi il thread in esecuzione a ogni ciclo di clock.
Per esempio:
- Ciclo i : l'istruzione j del thread A viene caricata
- Ciclo i+1 : l'istruzione k del thread B viene caricata
- Ciclo i+2 : l'istruzione h del thread C viene caricata
Questa tipologia di mutithreading 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-empiteve o interlaved o time-sliced o fine-grained multithreading.
Hardware costs
In addition to the hardware costs discussed in the Block type of multithreading, interleaved multithreading has an additional cost of each pipeline stage tracking the thread ID of the instruction it is processing. Also, since there are more threads being executed concurrently in the pipeline, shared resources such as caches and TLBs need to be larger to avoid thrashing between the different threads.
Examples
- Denelcor Heterogeneous Element Processor
- Sun Microsystems UltraSPARC T1
- Lexra NetVortex
- MIPS 34K core which implements the Multi-Threaded ASE
- Raza Microelectronics Inc XLR
Simultaneous multi-threading
See main article Simultaneous multithreading
Concept
The most advanced type of multi-threading applies to superscalar processors. A normal superscalar processor issues multiple instructions from a single thread every CPU cycle. In Simultaneous Multi-threading (SMT), the superscalar processor can issue instructions from multiple threads every CPU cycle. Recognizing that any single thread has a limited amount of instruction level parallelism, this type of multithreading is trying to exploit parallelism available across multiple threads to decrease the waste associated with unused issue slots.
For example:
- Cycle i : instructions j and j+1 from thread A; instruction k from thread B all simultaneously issued
- Cycle i+1: instruction j+2 from thread A; instruction k+1 from thread B; instruction m from thread C all simultaneously issued
- Cycle i+2: instruction j+3 from thread A; instructions m+1 and m+2 from thread C all simultaneously issued
Terminology
To distinguish the other flavors of multithreading from SMT, the term Temporal multithreading is used to denote when instructions from only one thread can be issued at a time.
Hardware costs
In addition to the hardware costs discussed for interleaved multithreading, SMT has the additional cost of each pipeline stage tracking the Thread ID of each instruction being processed. Again, shared resources such as caches and TLBs have to be sized for the large number of active threads.
Examples
- DEC Alpha EV8 (not completed)
- Intel Hyperthreading
- IBM POWER5
- Power Processing Elements within the Cell microprocessor
- Sun Microsystems UltraSPARC T2
Implementation specifics
A major area of research is the thread scheduler which must quickly choose among the list of ready-to-run threads to execute next as well as maintain the read-to-run and stalled thread lists. An important sub-topic are the different thread priority schemes that can be used by the scheduler. The thread scheduler might be implemented totally in software or totally in hardware or as a hw/sw combination.
Another area of research is what type of events should cause a thread switch - cache misses, inter-thread communication, DMA completion, etc.
If the multithreading scheme replicates all software visible state, include privileged control registers, TLBs, etc., then it enables virtual machines to be created for each thread. This allows each thread to run its own operating system on the same processor. On the other hand, if only user-mode state is saved, less hardware is required which would allow for more threads to be active at one time for the same die-area/cost.
See also
- Thread (computer science)
- Simultaneous multithreading, SMT
- Temporal multithreading, also known as Interleaved multi-threading
Hardware techniques used to support multithreading often parallel the software techniques used
for computer multitasking of computer programs.
