Il presente articolo è stato tradotto automaticamente.

Pool di thread

Programmazione multithreading scalabile con pool di thread

Ron Fosner

Programmazione quasi più complessa, in particolare se si lavora in un campo che è necessario ottimizzare l'applicazione per la velocità di trasmissione più veloce possibile. Un fattore di cause è che negli ultimi anni hanno visto una modifica nel modo che PC sono in continua evoluzione. Anziché affidarsi alla velocità sempre di un unico processore, la potenza di calcolo dei PC ora viene distribuita tra più core. Si tratta di una cosa positiva. Hefty aumento della potenza di elaborazione latente è ora disponibile a un costo relativamente basso e spesso con molto basso consumo di energia e alle esigenze di raffreddamento.

Ma c'è un svantaggio per la crescente prevalenza di base più sistemi. Per utilizzare più processori, è necessario approfondire il mondo dell'elaborazione parallela. Significa che richiede maggiore lavoro e a volte una curva di apprendimento significativa, per i programmatori sfruttare la potenza di elaborazione latente. È possibile generare alcuni parametri del compilatore nel progetto e ottenere il compilatore scrivere del codice multithreading è. Tuttavia, per poter sfruttare tutta la potenza dei computer multicore, è necessario apportare alcune modifiche in modo programmare i processi di grandi dimensioni.

Esistono diversi modi per distribuire il lavoro più core. Programmazione basata su attività viene chiamato uno dei più semplice e più affidabile. Le attività consentono di lavorare dell'applicazione e suddivisi in alcuni o tutti i core CPU disponibili. Con un po' di programmazione ponderate, è possibile ridurre o eliminare eventuali vincoli di dipendenza dei dati o la sincronizzazione dell'ora. Per raggiungere questo stato di bliss multicore, sarà necessario riesaminare alcuni di preconceptions di attaccare un problema di programmazione e ridefinire gestione realtà in termini di programmazione basata su attività.

Per visualizzare questo utilizzo, verrà consentono i passaggi e la missteps, impiegato nella conversione di un'applicazione a thread singolo a uno che è possibile scalare all'utilizzo di tutte le CPU disponibili in un computer. In questo articolo verrà presentare alcuni dei concetti di programmazione multithreading e illustrano alcuni modi semplici per introdurre l'esecuzione di thread nel codice con OpenMP e thread pool. Inoltre si vedrà come utilizzare Visual Studio 2010 per misurare il miglioramento delle prestazioni ottenute queste tecniche. In un articolo futuro, verrà creato tale basi per mostrare che più sofisticati multithreading eseguendo le attività.

Dai thread di attività

La sfida principale con una scala di programma che effettua il numero di Core CPU è che non solo decide generare alcuni processi nel proprio thread e consentire loro di eseguire. Infatti, è molto personale si ma solo le proporzioni per il numero di Core per cui l'applicazione è stata progettata. Non scalabile e con un numero inferiore o superiore al numero di Core erano destinati ed totalmente overlooks l'eliminazione incorporata engenders tale approccio.

Un modo migliore per assicurarsi che l'applicazione si adatta bene con un numero variabile di Core è violare più piccoli, di facile integrazione con i thread sottoprocessi denominati attività processi di grandi dimensioni. La parte più difficile della conversione di un programma a thread singolo monolitico o con alcuni thread dedicati in un sistema basato su attività di processo è effettivamente interrompere i processi in attività.

Sono riportate alcune indicazioni da tenere presenti durante la conversione di un processo a thread singolo grande in operazioni con multithreading:

  • The large job can be arbitrarily divided into 1 to n tasks.
  • L'attività deve essere in grado di eseguire in qualsiasi ordine.
  • Le attività devono essere indipendenti tra loro.
  • Le attività devono essere associati a dati di contesto.

Se tutti questi semplici, non si avrà alcun problema rendendo le applicazioni eseguite su qualsiasi numero di Core. Purtroppo non tutti i problemi possono essere suddiviso in modo perfettamente in attività che soddisfano queste linee guida.

Queste indicazioni sono importanti quanto se seguita, consentono di eseguire in modo indipendente ogni attività su un thread con nessuna dipendenza tra le attività. In teoria attività devono essere in grado di essere eseguito in qualsiasi ordine, eliminando o riducendo le interdipendenze è fondamentale da effettuare per eseguire un sistema basato su attività.

La maggior parte delle applicazioni reali passa attraverso varie fasi di elaborazione, con ogni fase necessaria per il completamento prima di avviare la fase successiva. Questi punti di sincronizzazione sono spesso inevitabili, ma con un sistema basato su attività che l'obiettivo consiste nell'assicurarsi di che usufruire di qualsiasi potenza della CPU è immediatamente disponibile. Con alcune importanti razionale dei processi di grandi dimensioni piccole, è spesso possibile avviare intermingling alcuni risultati di attività completate con la fase successiva di elaborazione mentre le operazioni iniziali sono ancora in esecuzione.

Semplice multithreading con OpenMP

Prima di convertire l'intera applicazione per utilizzare le attività, è necessario essere consapevoli di altri modi per ottenere alcuni vantaggi di multithreading senza passare attraverso l'esercizio rigoroso di rendere tutto un'attività. Esistono numerosi modi per incorporare nelle applicazioni multithreading, molti richiedono sforzo effettivo, ma che consentono di trarre vantaggio dall'aggiunta di multithreading al codice.

OpenMP è uno dei modi più semplici per aggiungere i programmi di elaborazione parallela e supportata dal compilatore c ++ di Visual Studio dal 2005. Si attiva OpenMP aggiungendo codice per indicare dove pragma e qual è il parallelismo che si desidera aggiungere. Ad esempio, è possibile aggiungere il parallelismo per un semplice programma Hello World:

#include <omp.h> // You need this or it won't work
#include <stdio.h>
int main (int argc, char *argv[]) {
  #pragma omp parallel
  printf("Hello World from thread %d on processor %d\n",
    ::GetCurrentThreadfID(), 
    ::GetCurrentProcessorNumber());
  return 0;
}

Il pragma OpenMP parallelizes il blocco di codice successivo, in questo caso si tratta semplicemente di printf, e viene eseguita contemporaneamente su tutti i thread di hardware. Il numero di thread dipenderanno dal numero di thread di hardware è disponibile sul computer. L'output è un'istruzione printf in esecuzione su ogni thread hardware.

Per ottenere qualsiasi programma OpenMP per parallelizzare (e non automaticamente ignora i pragma OpenMP), è necessario attivare OpenMP per il programma. Innanzitutto, è necessario includere l'opzione del compilatore /openmp (proprietà | C/C ++ | Language | Apri supporto Multiprocessore). In secondo luogo, è necessario includere il file di intestazione omp.h.

Dove proviene realmente OpenMP è quando l'applicazione trascorre la maggior parte del suo tempo ciclo tramite funzioni o dati e si desidera aggiungere il supporto multiprocessore. Ad esempio, se si dispone di un ciclo che richiede molto tempo per l'esecuzione, è possibile utilizzare OpenMP per facilmente parallelizzare il ciclo. Ecco un esempio che interrompe il calcolo di matrice e li distribuisce tra il numero di Core disponibili automaticamente:

#pragma omp parallel for
for (int i = 0; i < 50000; i++)
  array[i] = i * i;

OpenMP presenta altri costrutti che consentono un maggiore controllo sul numero di thread creati, se il lavoro distribuito deve terminare prima che venga eseguito il blocco di codice successivo, creazione di dati locale di thread, punti di sincronizzazione, le sezioni critiche e così via.

Come si può vedere, OpenMP è un modo semplice per introdurre delicatamente parallelismo in una base di codice esistente. Tuttavia, mentre la semplicità di OpenMP è interessante, esistono casi che occorre controllare meglio ciò che sta eseguendo l'applicazione, ad esempio quando si desidera modificare dinamicamente le operazioni eseguite oppure è necessario assicurarsi che un thread rimane in un particolare di base. OpenMP è progettato per integrare facilmente alcuni aspetti della programmazione multithread del programma, ma non dispone di alcune delle funzionalità avanzate che è necessario per ottenere un utilizzo ottimale di uscita multicore sono disponibili. È in cui entrano attività e i pool di thread.

Utilizzo del pool di thread

Thread richiedono una grande quantità di operazioni dal sistema operativo, pertanto non è consigliabile creare e distruggere li wantonly. Esistono non significativi dei costi associati alla creazione e all'eliminazione di un thread, pertanto in questo caso costantemente, è facile perdere alcun vantaggio ottenuto dal multithreading.

Invece, è preferibile utilizzare un insieme di thread riciclata, se necessario, per tutte le attività a tema esistente. Questa struttura è chiamata un pool di thread e Windows fornisce uno da utilizzare. Utilizzando questo pool di thread evita di dover gestire thread di creazione, eliminazione e gestione che viene gestito automaticamente dal pool di thread. OpenMP utilizza un pool di thread per distribuire il lavoro con thread e Windows Vista e Windows 7 forniscono versioni ottimizzate del pool di thread da utilizzare direttamente.

Mentre è possibile creare pool di thread, che potrebbe essere necessario se avete insolite alcuni requisiti di pianificazione, si è molto meglio utilizzando uno fornito dal sistema operativo o Microsoft .NET Framework.

A questo punto è necessario chiarire alcuni terminologia. Quando molte persone parlare di un thread, fa riferimento al flusso di esecuzione tramite un singolo core CPU, in altre parole, un thread di software. Su una CPU, il flusso di esecuzione (l'esecuzione effettiva di istruzioni) si verifica sul thread dell'hardware. Il numero di thread hardware è limitato dall'applicazione è in esecuzione su hardware. Nei giorni precedenti, questa era una CPU a thread singolo, ma ora è comune per i sistemi con processori dual-core almeno. Una CPU quattro principali avranno la possibilità di eseguire thread hardware quattro o otto se hyperthreaded. Sistemi desktop high-end vanta oltre 16 thread hardware e alcune configurazioni server dispone di più di 100!

Mentre un thread hardware esegue effettivamente le istruzioni, un thread di software si riferisce all'intero contesto — registrano valori e gestisce gli attributi di protezione e così via, necessarie per eseguire effettivamente il processo su un thread di hardware. È importante notare che è possibile avere molte più thread di software più thread hardware e si tratta di base sottostante di un pool di thread. Consente di accodare le attività di thread di software e pianificare vengano eseguite su thread hardware effettivo.

Il vantaggio di utilizzare un pool di thread anziché crearne di propri thread è il sistema operativo verrà occuparsi della pianificazione delle attività, il lavoro, è necessario mantenere alimentazione attività nel pool di thread in modo che il sistema operativo sarà in grado di mantenere tutti i thread hardware occupato. Questo scenario è illustrato nella Figura 1. Tutti gli elementi della finestra costituisce il pool di thread ed è all'esterno dell'area di autenticazione del programmatore. Spetta all'applicazione all'avanzamento delle attività nel pool di thread, dove vengono collocati nella coda di thread e infine pianificati per essere eseguito su un thread di hardware.

image: A Thread Pool

Figura 1 di un pool di thread

Ora si ottiene la parte difficile: Qual è il modo migliore per i processi di struttura per tenere occupato i core e l'utilizzo della CPU al massimo? Questo dipende l'applicazione deve eseguire.

Lavoro frequentemente con società di videogiochi e questi sono alcuni dei tipi più complessi di applicazioni su cui lavorare perché non vi è una grande quantità di lavoro per il, in genere alcuni in un determinato ordine seriale, e sono riservato a ritardi. Poiché è in genere un determinato tasso di frame in cui verrà automaticamente aggiornato, se la frequenza di frame avvia cadere, presenta l'esperienza di gioco. Di conseguenza, è molto incentivo per ottimizzare l'utilizzo dell'hardware.

D'altra parte, se l'applicazione è una cosa di grandi dimensioni alla volta, è un po' più ovvia è necessario, ma è comunque difficile tenta di distribuire un singolo processo core multipli.

Ordinamento con multithreading

Primo let’s esaminiamo un processo monolitico disponibile frequentemente in applicazioni e vedere come è possibile passare informazioni trasformandolo in un formato più descrittivo di con multithreading. Sto pensando, naturalmente, l'ordinamento. L'ordinamento è un esempio particolarmente efficace perché ha un ostacolo principale: Come Ordina qualcosa e distribuito l'ordinamento attraverso multicore in modo che l'ordinamento su una base è indipendente dalle quali ordinamento sulla base di un altro?

Un approccio naïve spesso visualizzato consiste nel bloccare l'accesso a tutti i dati accessibili core multipli con qualcosa di simile a un mutex, il semaforo o la sezione critica. Questa soluzione funzionerà. Tuttavia, se viene utilizzata come una panacea per la programmazione dell'accesso ai dati condivisi non correttamente, nel migliore dei casi si sarà finisce eliminare eventuali guadagni che potrebbe avere ottenuto bloccando gli altri thread di eseguire. Nel peggiore dei casi, si potrebbe introdurre alcuni impercettibile race condition che sarà excruciatingly difficile tenere traccia.

Fortunatamente, è possibile progettare l'applicazione per eliminare la maggior parte dell'accesso ai dati condiviso tra thread scegliendo l'algoritmo di ordinamento appropriato.

Un approccio migliore consiste nell'assegnare ciascun core una sottosezione della matrice da ordinare. Questo metodo di divisione e conquistare è un modo semplice per distribuire lo stesso set di dati di lavoro core multipli. Gli algoritmi di ordinamento unione e ordinamento rapido utilizzare una strategia di divisione e conquistare e sono semplici da implementare in modo che si avvale di un sistema multicore.

Let’s osservare come ordinamento unione funziona sulla stringa di valori integer casuali visualizzati in di Figura 2. Il primo passo è scegliere un punto centrale di matrice e dividere in due sottoelenchi. Mantieni fino a quando non si dispone di elenchi sono zero o un elemento di divisione.

image: Sorting a String of Random Integers

Figura 2 ordinamento una stringa di valori integer casuali

Nella maggior parte delle implementazioni, è effettivamente un limite dimensione elenco sotto il quale si dispone di un algoritmo efficiente progettato per gli elenchi di piccole dimensioni, ma funziona anche se mantenere dividendo solo fino a quando non è possibile dividere più. La cosa importante da tenere presente è che dopo un elenco si divide in due sottoelenchi, gli elenchi sono indipendenti. Come illustrato da linee tratteggiate rosse in di Figura 2. Una volta dvide elenco in sottoelenchi, ogni sottoelenco è indipendente ed è possibile assegnare a ciascuno di essi per una CPU nel gestire piace senza dover bloccare qualsiasi.

Per effettuare l'ordinamento più efficiente possibile, selezionare un algoritmo che accetta ogni sottoelenco e ordinare in posizione. È importante non solo per evitare inutili copia dei dati, ma anche per mantenere i dati a caldo in cache di secondo livello della CPU. Come si impegna a scrivere codice parallelo più efficiente, sono infine essere a conoscenza delle modalità di dati ottiene scambio e verso la cache di secondo livello, è in genere più moderni processori circa 256 KB.

Esistono molti algoritmi di ordinamento prestito stessi di parallelizzazione. Ordinamento rapido, selezione ordinamento, ordinamento unione e ordinamento radice sono tutti gli algoritmi che consentono di suddividere i dati e di operano in modo indipendente su di esso. Pertanto let’s esaminare un'implementazione di una routine di ordinamento seriale e convertirla in una parallela.

In teoria, una volta mantenere suddivisione in modo ricorsivo una matrice è infine finirà con un solo elemento. A questo punto, non nulla da ordinare, quindi l'algoritmo viene spostata nel passaggio successivo, che è l'unione sottoelenchi ordinati insieme. I singoli elementi vengono uniti in elenchi più grandi e ordinati. Questi ordinati sottoelenchi quindi vengono unite in elenchi ordinati anche superiori fino a ottenere la matrice originale in modo ordinato. Come accennato in precedenza, è generalmente più veloce per passare a un algoritmo che è ottimizzato per ordinare elenchi di piccole dimensioni quando l'elenco raggiunge una determinata soglia.

Esistono molti modi per scrivere un algoritmo di ordinamento e ho scelto di scrivere una routine di ordinamento rapido semplice in C#, come illustrato in di Figura 3. Questo programma consente di riempire una matrice di grandi dimensioni con la stessa sequenza di numeri casuali e ordinati utilizzando una routine di ordinamento rapido segnalato il tempo impiegato.

Figura 3 Quick Sort

 

using System;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;
namespace ParallelSort {
  class Program {
    // For small arrays, use Insertion Sort
    private static void InsertionSort(
      int[] list, int left, int right) {
      for (int i = left; i < right; i++) {
        int temp = list[i];
        int j = i;
        while ((j > 0) && (list[j - 1] > temp)) {
          list[j] = list[j - 1];
          j = j - 1;
        }
        list[j] = temp;
      }
    }
    private static int Partition(
      int[] array, int i, int j) {
      int pivot = array[i];
      while (i < j) {
        while (array[j] >= pivot && i < j) {
          j--;
        }
        if (i < j) {
          array[i++] = array[j];
        }
        while (array[i] <= pivot && i < j) {
          i++;
        }
        if (i < j) {
          array[j--] = array[i];
        }
      }
      array[i] = pivot;
      return i;
    }
    static void QuickSort(
      int[] array, int left, int right) {
      // Single or 0 elements are already sorted
      if (left >= right)
        return;
      // For small arrays, use a faster serial routine
      if ( right-left <= 32) {
        InsertionSort(array, left, right);
        return;
      }
      // Select a pivot, then quicksort each sub-array
      int pivot = Partition(array, left, right);
      QuickSort(array, left, pivot - 1);
      QuickSort(array, pivot + 1, right);
    }
    static void Main(string[] args) {
      const int ArraySize = 50000000;
      for (int iters = 0; iters < 1; iters++) {
        int[] array;
        Stopwatch stopwatch;
        array = new int[ArraySize];
        Random random1 = new Random(5);
        for (int i = 0; i < array.Length; ++i) {
          array[i] = random1.Next();
        }
        stopwatch = Stopwatch.StartNew();
        QuickSort(array, 0, array.Length - 1);
        stopwatch.Stop();
        // Verify it is sorted
        for (int i = 1; i < array.Length; ++i) 
          if (array[i - 1] > array[i - 1]) 
            throw new ApplicationException("Sort Failed");
        Console.WriteLine("Serialt: {0} ms",  
           stopwatch.ElapsedMilliseconds);
      }
    }
  }
}

Se si osserva la funzione QuicSort, si noterà che la matrice in due viene diviso in modo ricorsivo finché non viene raggiunta una soglia, a quel punto Ordina l'elenco senza ulteriore suddivisione. Se si modifica una versione parallela, sarà sufficiente è modificare le due righe seguenti:

QuickSort( array, lo, pivot - 1);
QuickSort( array, pivot + 1, hi);

La versione parallelizzata è:

Parallel.Invoke(
  delegate { QuickSort(array, left, pivot - 1); },
  delegate { QuickSort(array, pivot + 1, right); }
);

 

L'interfaccia Parallel.Invoke è parte dello spazio dei nomi Systems.Threading.Tasks trovato nella libreria Parallel utilità NET. Consente di specificare una funzione da eseguire in modo asincrono. In questo caso, stabilire si desidera eseguire ciascuna funzione di ordinamento su un thread separato.

Mentre sarebbe più efficace per generare solo un nuovo thread e utilizzare il thread corrente di esecuzione per ordinare altre sottoelenco, volevo mantenere la simmetria e illustrare come è semplice per convertire un programma seriale in un'applicazione parallela.

Utilizzo di base

La prossima domanda ovvia è: La parallelizzazione prestazioni è state migliorate affatto?

Visual Studio 2010 include numerosi strumenti per aiutare a comprendere in cui il programma è dedicare tempo e come si comporta come un'applicazione con multithreading. There’s a great introduction to using these tools for measuring the performance of your multithreaded app with Visual Studio 2010 in the September 2009 MSDN Magazine article “Debugging Task-Based Parallel Applications in Visual Studio 2010” by Stephen Toub and Daniel Moth (msdn.microsoft.com/magazine/ee410778), plus there’s a good video introduction by Daniel Moth on Channel 9 (channel9.msdn.com/posts/DanielMoth/Parallel-Tasks--new-Visual-Studio-2010-debugger-window/).

Programmazione parallela è necessario apportare effettivamente le misure che è realmente migliorate prestazioni e utilizzano l'hardware. Per ulteriori informazioni su come parallelizzazione veniva utilizzato nell'applicazione di esempio, let’s utilizzare questi strumenti per misurare le routine di ordinamento in azione. Avviata la guidata di Visual Studio 2010 Performance eseguire misurazioni di concorrenza di ordinamento dell'applicazione durante l'esecuzione.

La prima cosa da esaminare è l'utilizzo di base, che mostra come i cicli viene effettuata l'utilizzo della CPU disponibile. Il programma di test viene eseguito l'ordinamento seriale, resta inattivo per un secondo, quindi esegue la versione parallela dell'ordinamento. Sul mio computer principale 4 viene visualizzato il grafico di utilizzo principali visualizzato in di Figura 4. Il verde è l'applicazione giallo è il sistema operativo e da altri programmi e grigio è inattivo. Linea piatta a livello base 1 mostra che completamente saturi l'elaborazione su un singolo core durante l'esecuzione della versione seriale e viene visualizzato su 2,25 di quattro Core quando si esegue la versione parallela. Il tempo necessario per eseguire l'ordinamento parallela è troppo ovviamente 45% circa del tempo necessario per l'ordinamento seriale. Non troppo shabby per modificare due righe di codice.

image: Core Utilization

Figura 4 di utilizzo principali

A questo punto, passare let’s da osservare il grafico di utilizzo della CPU alla visualizzazione thread illustrato in Figura 5 , che mostra come l'applicazione utilizzati thread disponibili. Si noti che è presente un singolo thread per la maggior parte del tempo di esecuzione. È non fino a quando non si avvia generazione di operazioni di creazione di più thread. In questa visualizzazione il colore salmon indica un thread è stato bloccato da un altro thread.

image: Thread Work

Figura 5 thread di lavoro

Visualizzazione thread indica infatti che mentre ha ricevuto un aumento significativo nella velocità di esecuzione, non molto efficiente. È perfettamente a un blocco di thread in attesa di altri thread mentre il thread principale attende il completamento delle attività. Tuttavia, ciò che si desidera vedere è verde a tinta unita in numero di attività dispone di Core CPU. Pertanto, anche se il grafico di utilizzo della CPU Mostra l'utilizzo migliore di Core CPU quando si scatta vicino come attività sono state distribuite in tutto il pool di thread, vedere spazio per un'ulteriore ottimizzazione.

Infatti, si dovrebbe misura il codice per le prestazioni sempre dopo che è stato svolto un lavoro di multithreading, funzionano anche semplice come ho fatto qui. Per i processi di piccole dimensioni, non si desidera con multithreading perché l'overhead verrà sovraccaricare le prestazioni di threading. Per i processi di dimensioni maggiori, sarà necessario suddividere il lavoro in tanti Core CPU sono disponibili all'utente così come non oversubscribe il pool di thread.

Quali Avanti?

Esistono diversi modi per ottenere prestazioni migliori anche all'esterno del codice, ma non è l'obiettivo di questo articolo iniziale. Ma si spiegato come ottenere l'80% di utilizzo della CPU per apportare solo alcune modifiche al codice che lo rendono adatto al thread. Invece di ottimizzare ulteriormente questo codice, tuttavia, ci concentreremo durante il recupero massime prestazioni della CPU di un sistema dall'architettura dei processi in modo leggermente diverso.

L'ordinamento in modo ho dimostrato qui è particolarmente amenable nelle operazioni multithread. Per calcolare la distanza che si desidera dividere il processo e assegnare ogni sub-job a un thread. Tuttavia, mentre ha ricevuto un incremento delle prestazioni, tralasciare le prestazioni.

Ma in applicazioni reali, che è possibile eseguire in una situazione in cui sono presenti sia molti processi di assegnare gruppi di attività univoco, o forse non sapere quanto tempo alcuna particolare operazione è passare per eseguire e di dover pianificare attività intorno a questa incertezza. È un problema particolarmente impegnativo. Nel mio prossimo articolo, illustrerò esaminare un'architettura che adotta un approccio olistico al threading, che consente di distribuire più probabilmente diversi processi. Viene illustrato come architettura di un'applicazione per renderla compatibile con multicore dall'inizio l'utilizzo di attività e i pool di thread.

Ron Fosner è l'ottimizzazione delle applicazioni a elevate prestazioni e giochi in Windows per 20 anni e avvio di ottenere blocchi di it. È una grafica e ottimizzazione esperto a Intel e happiest quando si rileva tutti i core CPU esegue piatto out. You can reach him at Ron@directx.com.

Grazie all'esperto di tecnica seguente per la revisione di questo articolo: Stephen Toub