Algoritmi paralleli

 

Per la documentazione più recente di Visual Studio 2017 RC, vedere Documentazione di Visual Studio 2017 RC.

La libreria PPL (Parallel Patterns Library) fornisce gli algoritmi che vengono eseguite contemporaneamente su raccolte di dati. Questi algoritmi sono simili a quelli forniti dalla libreria di modelli Standard (STL).

Gli algoritmi paralleli sono costituiti da funzionalità esistenti nel Runtime di concorrenza. Ad esempio, il Concurrency:: parallel_for algoritmo utilizza un Concurrency:: structured_task_group oggetto per eseguire le iterazioni del ciclo parallelo. Il parallel_for algoritmo partiziona il lavoro in modo ottimale in base al numero di risorse di elaborazione disponibili.

Il Concurrency:: parallel_for algoritmo esegue ripetutamente la stessa attività in parallelo. Ognuna di queste attività con i parametri di un valore di iterazione. Questo algoritmo è utile quando si dispone di un corpo del ciclo che non condividono le risorse tra le iterazioni del ciclo.

Il parallel_for algoritmo le attività in modo ottimale per l'esecuzione parallela. Viene utilizzato un algoritmo di acquisizione del lavoro e di acquisizione dell'intervallo per bilanciare le partizioni quando i carichi di lavoro non sono bilanciati. Quando un'iterazione del ciclo viene bloccato in modo cooperativo, il runtime ridistribuisce l'intervallo di iterazioni che viene assegnato al thread corrente per altri thread o processori. Analogamente, quando un thread viene completato un intervallo di iterazioni, il runtime ridistribuisce il lavoro da altri thread per tale thread. Il parallel_for algoritmo supporta inoltre annidati parallelismo. Quando un ciclo parallelo contiene un altro ciclo parallelo, il runtime coordina le risorse di elaborazione tra i corpi di ciclo in modo efficiente per l'esecuzione parallela.

Nell'algoritmo parallel_for sono disponibili diverse versioni di overload. La prima versione accetta un valore iniziale, un valore finale e una funzione lavoro (un'espressione lambda, oggetti funzione o puntatore a funzione). La seconda versione accetta un valore iniziale, un valore finale, un valore che al passaggio e una funzione lavoro. La prima versione di questa funzione utilizza 1 come valore di incremento. Le versioni rimanenti accettano oggetti di partizionamento che consentono di specificare il modo in cui gli intervalli devono essere partizionati tra i thread tramite l'algoritmo parallel_for. I partitioner sono descritti più dettagliatamente nella sezione partizionamento del lavoro in questo documento.

È possibile convertire molti for cicli utilizzare parallel_for. Tuttavia, il parallel_for rispetto all'algoritmo di for istruzione nei modi seguenti:

  • Il parallel_for algoritmo parallel_for non esegue le attività in un ordine predeterminato.

  • Il parallel_for algoritmo non supporta le condizioni di terminazione arbitraria. Il parallel_for algoritmo si interrompe quando il valore della variabile di iterazione corrente è minore di last.

  • Il _Index_type parametro di tipo deve essere un tipo integrale. Questo tipo integrale può essere firmato o non firmato.

  • L'iterazione del ciclo deve essere in avanti. Il parallel_for algoritmo genera un'eccezione di tipo std:: invalid_argument Se il _Step parametro è minore di 1.

  • Il meccanismo di gestione delle eccezioni per il parallel_for algoritmo è diverso da quello di un for ciclo. Se si verificano più eccezioni contemporaneamente in un corpo del ciclo parallelo, il runtime propaga solo una delle eccezioni per il thread che ha chiamato parallel_for. Inoltre, quando un'iterazione del ciclo genera un'eccezione, il runtime non interrompe immediatamente il ciclo globale. Al contrario, il ciclo viene inserito nello stato annullato e il runtime elimina tutte le attività che non hanno ancora avviato. Per ulteriori informazioni sulla gestione delle eccezioni e sugli algoritmi paralleli, vedere Exception Handling.

Sebbene il parallel_for algoritmo non supporta le condizioni di terminazione arbitraria, è possibile utilizzare l'annullamento per interrompere tutte le attività. Per ulteriori informazioni sull'annullamento, vedere annullamento.

System_CAPS_ICON_note.jpg Nota

Il costo di pianificazione che i risultati di bilanciamento del carico e supporto per funzionalità quali annullamento potrebbero non superare i vantaggi dell'esecuzione del corpo del ciclo in parallelo, soprattutto quando il corpo del ciclo è relativamente piccolo. È possibile ridurre al minimo questo sovraccarico utilizzando un partitioner nel ciclo parallelo. Per ulteriori informazioni, vedere partizionamento del lavoro più avanti in questo documento.

Esempio

Nell'esempio seguente viene illustrata la struttura di base di parallel_for algoritmo. In questo esempio viene stampato nella console il valore nell'intervallo [1, 5] in parallelo.

// parallel-for-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Print each value from 1 to 5 in parallel.
   parallel_for(1, 6, [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

Questo esempio produce il seguente output di esempio:

1 2 4 3 5  

Poiché il parallel_for algoritmo agisce su ogni elemento in parallelo, l'ordine in cui i valori vengono visualizzati nella console possono variare.

Per un esempio completo che utilizza il parallel_for algoritmo, vedere procedura: scrivere un ciclo parallel_for.

[Torna all'inizio]

Il Concurrency:: parallel_for_each algoritmo esegue le attività in un contenitore iterativo, ad esempio quelle fornite dalla libreria STL, in parallelo. Usa la stessa logica di partizionamento che il parallel_for algoritmo utilizza.

Il parallel_for_each è simile all'algoritmo STL std:: for_each algoritmo, tranne il fatto che il parallel_for_each algoritmo esegue le attività contemporaneamente. Come altri algoritmi paralleli, parallel_for_each esegue le attività in un ordine specifico.

Sebbene il parallel_for_each algoritmo funziona in entrambi gli iteratori in avanti e gli iteratori ad accesso casuale, le prestazioni sono migliori con gli iteratori ad accesso casuale.

Esempio

Nell'esempio seguente viene illustrata la struttura di base di parallel_for_each algoritmo. In questo esempio viene stampato nella console il valore in un std:: Array oggetto in parallelo.

// parallel-for-each-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Create an array of integer values.
   array<int, 5> values = { 1, 2, 3, 4, 5 };

   // Print each value in the array in parallel.
   parallel_for_each(begin(values), end(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}
/* Sample output:
   5 4 3 1 2
*/

Questo esempio produce il seguente output di esempio:

4 5 1 2 3  

Poiché il parallel_for_each algoritmo agisce su ogni elemento in parallelo, l'ordine in cui i valori vengono visualizzati nella console possono variare.

Per un esempio completo che utilizza il parallel_for_each algoritmo, vedere procedura: scrivere un ciclo parallel_for_each.

[Torna all'inizio]

Il Concurrency:: parallel_invoke algoritmo esegue un set di attività in parallelo. Non restituisce fino al termine di ogni attività. Questo algoritmo è utile quando si dispone di più attività indipendenti che si desidera eseguire contemporaneamente.

Il parallel_invoke algoritmo accetta come parametri una serie di funzioni di lavoro (funzioni lambda, oggetti funzione o puntatori a funzione). Il parallel_invoke algoritmo è in overload per accettare da due a dieci parametri. Ogni funzione che viene passato a parallel_invoke deve accettare zero parametri.

Come altri algoritmi paralleli, parallel_invoke esegue le attività in un ordine specifico. L'argomento parallelismo delle attività viene illustrato come il parallel_invoke algoritmo correlato alle attività e gruppi di attività.

Esempio

Nell'esempio seguente viene illustrata la struttura di base di parallel_invoke algoritmo. In questo esempio vengono chiamati simultaneamente il twice funzione tre variabili locali e stampi il risultato nella console.

// parallel-invoke-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <string>
#include <iostream>

using namespace concurrency;
using namespace std;

// Returns the result of adding a value to itself.
template <typename T>
T twice(const T& t) {
   return t + t;
}

int wmain()
{
   // Define several values.
   int n = 54;
   double d = 5.6;
   wstring s = L"Hello";

   // Call the twice function on each value concurrently.
   parallel_invoke(
      [&n] { n = twice(n); },
      [&d] { d = twice(d); },
      [&s] { s = twice(s); }
   );

   // Print the values to the console.
   wcout << n << L' ' << d << L' ' << s << endl;
}

Questo esempio produce il seguente output:

108 11.2 HelloHello  

Per esempi completi che utilizzano il parallel_invoke algoritmo, vedere procedura: utilizzare parallel_invoke per scrivere una Routine di ordinamento parallelo e procedura: utilizzare parallel_invoke per eseguire operazioni in parallelo.

[Torna all'inizio]

Il Concurrency:: parallel_reduce e Concurrency:: parallel_transform algoritmi sono versioni parallele degli algoritmi STL std:: Transform e std:: accumulate, rispettivamente. Le versioni del runtime di concorrenza si comportano come le versioni della libreria STL, tuttavia l'ordine delle operazioni non viene determinato in quanto vengono eseguite in parallelo. Sfruttare questi algoritmi quando si utilizza un set sufficientemente grande da ottenere vantaggi di scalabilità e di prestazioni dall'esecuzione in parallelo.

System_CAPS_ICON_important.jpg Importante

Gli algoritmi parallel_transform e parallel_reduce supportano solo iteratori di accesso casuale, bidirezionale e di inoltro perché tramite questi iteratori vengono generati indirizzi di memoria stabili. Inoltre, tramite questi iteratori devono essere generati valori l-value non const.

L'algoritmo parallel_transform

È possibile utilizzare l'algoritmo parallel transform per eseguire molte operazioni di parallelizzazione dati. Ad esempio, è possibile eseguire queste operazioni:

  • Regolare la luminosità di un'immagine ed eseguire altre operazioni di elaborazione immagini.

  • Sommare o eseguire il prodotto scalare di due vettori e altri calcoli numerici con i vettori.

  • Eseguire il ray tracing 3D in cui per ogni iterazione viene fatto riferimento a un pixel di cui deve essere eseguito il rendering.

Nell'esempio seguente viene mostrata la struttura di base utilizzata per chiamare l'algoritmo parallel_transform. Questo esempio viene negato ogni elemento di un std::vettore oggetto in due modi. Nel primo viene utilizzata un'espressione lambda. Il secondo modo utilizza std:: negate, che deriva da std:: unary_function.

// basic-parallel-transform.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create a large vector that contains random integer data.
    vector<int> values(1250000);
    generate(begin(values), end(values), mt19937(42));

    // Create a vector to hold the results.
    // Depending on your requirements, you can also transform the 
    // vector in-place.
    vector<int> results(values.size());

    // Negate each element in parallel.
    parallel_transform(begin(values), end(values), begin(results), [](int n) {
        return -n;
    });

    // Alternatively, use the negate class to perform the operation.
    parallel_transform(begin(values), end(values), begin(values), negate<int>());
}

System_CAPS_ICON_warning.jpg Avviso

In questo esempio viene mostrato l'utilizzo di base di parallel_transform. Poiché tramite la funzione di lavoro non viene eseguita una quantità significativa di lavoro, in questo esempio non è previsto un miglioramento significativo delle prestazioni.

Nell'algoritmo parallel_transform sono disponibili due overload. Il primo accetta un intervallo di input e una funzione unaria. La funzione unaria può essere un'espressione lambda che accetta un argomento, un oggetto funzione o un tipo che deriva da unary_function. Il secondo accetta due intervalli di input e una funzione binaria. La funzione binaria può essere un'espressione lambda che accetta due argomenti, un oggetto funzione o un tipo che deriva da std:: binary_function. Nell'esempio seguente vengono illustrate queste differenze.

    //
    // Demonstrate use of parallel_transform together with a unary function.

    // This example uses a lambda expression.
    parallel_transform(begin(values), end(values), 
        begin(results), [](int n) { 
            return -n;
        });

    // Alternatively, use the negate class:
    parallel_transform(begin(values), end(values), 
        begin(results), negate<int>());

    //
    // Demonstrate use of parallel_transform together with a binary function.

    // This example uses a lambda expression.
    parallel_transform(begin(values), end(values), begin(results), 
        begin(results), [](int n, int m) {
            return n * m;
        });

    // Alternatively, use the multiplies class:
    parallel_transform(begin(values), end(values), begin(results), 
        begin(results), multiplies<int>());

System_CAPS_ICON_important.jpg Importante

L'iteratore fornito per l'output di parallel_transform deve sovrapporsi completamente all'iteratore di input o non sovrapporsi affatto. Il comportamento di questo algoritmo non è specificato se gli iteratori di input e di output si sovrappongono parzialmente.

L'algoritmo parallel_reduce

L'algoritmo parallel_reduce è utile quando si dispone di una sequenza di operazioni che soddisfano la proprietà associativa; (per questo algoritmo non è richiesta la proprietà commutativa). Di seguito sono elencate alcune delle operazioni che è possibile eseguire con parallel_reduce:

  • Moltiplicare sequenze di matrici per generare una matrice.

  • Moltiplicare un vettore per una sequenza di matrici per generare un vettore.

  • Calcolare la lunghezza di una sequenza di stringhe.

  • Combinare un elenco di elementi, ad esempio stringhe, in un unico elemento.

Nell'esempio di base seguente viene illustrato come utilizzare l'algoritmo parallel_reduce per combinare una sequenza di stringhe in una unica. Come negli esempi di parallel_transform, i miglioramenti delle prestazioni non sono previsti in questo esempio di base.

// basic-parallel-reduce.cpp
// compile with: /EHsc
#include <ppl.h>
#include <iostream>
#include <string> 
#include <vector>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create a vector of strings.
    vector<wstring> words;
    words.push_back(L"Lorem ");
    words.push_back(L"ipsum ");
    words.push_back(L"dolor ");
    words.push_back(L"sit ");
    words.push_back(L"amet, ");
    words.push_back(L"consectetur ");
    words.push_back(L"adipiscing ");
    words.push_back(L"elit.");

    // Reduce the vector to one string in parallel.
    wcout << parallel_reduce(begin(words), end(words), wstring()) << endl;
}

/* Output:
   Lorem ipsum dolor sit amet, consectetur adipiscing elit.
*/

In molti casi, è possibile pensare parallel_reduce come una sintassi abbreviata per l'utilizzo del parallel_for_each algoritmo con il Concurrency:: combinable (classe).

Esempio: Esecuzione del mapping e riduzione in parallelo

Oggetto mappa operazione applica una funzione a ogni valore di una sequenza. Oggetto ridurre operazione combina gli elementi di una sequenza in un unico valore. È possibile utilizzare il modello libreria STL (Standard) std:: Transformstd:: accumulate classi per eseguire mapping e riduzione delle operazioni. Tuttavia, per molti problemi, è possibile utilizzare l'algoritmo parallel_transform per eseguire l'operazione di mapping in parallelo e l'algoritmo parallel_reduce per eseguire l'operazione di riduzione in parallelo.

Nell'esempio seguente viene confrontato il tempo necessario per calcolare la somma dei numeri primi in serie e in parallelo. Nella fase di mapping i valori non primi vengono trasformati in 0, mentre in quella di riduzione i valori vengono sommati.

// parallel-map-reduce-sum-of-primes.cpp
// compile with: /EHsc
#include <windows.h>
#include <ppl.h>
#include <array>
#include <numeric>
#include <iostream>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

// Determines whether the input value is prime.
bool is_prime(int n)
{
   if (n < 2)
      return false;
   for (int i = 2; i < n; ++i)
   {
      if ((n % i) == 0)
         return false;
   }
   return true;
}

int wmain()
{   
   // Create an array object that contains 200000 integers.
   array<int, 200000> a;

   // Initialize the array such that a[i] == i.
   iota(begin(a), end(a), 0);

   int prime_sum;
   __int64 elapsed;

   // Compute the sum of the numbers in the array that are prime.
   elapsed = time_call([&] {
       transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = accumulate(begin(a), end(a), 0);
   });   
   wcout << prime_sum << endl;   
   wcout << L"serial time: " << elapsed << L" ms" << endl << endl;

   // Now perform the same task in parallel.
   elapsed = time_call([&] {
      parallel_transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = parallel_reduce(begin(a), end(a), 0);
   });
   wcout << prime_sum << endl;
   wcout << L"parallel time: " << elapsed << L" ms" << endl << endl;
}
/* Sample output:
   1709600813
   serial time: 7406 ms
   
   1709600813
   parallel time: 1969 ms
*/

Per un altro esempio che esegue una mappa e ridurre l'operazione in parallelo, vedere procedura: eseguire mappa e ridurre le operazioni in parallelo.

[Torna all'inizio]

Per parallelizzare un'operazione su un'origine dati, è un passaggio essenziale partizione l'origine in più sezioni a cui è possibile accedere contemporaneamente da più thread. Tramite un partitioner viene specificato il modo in cui gli intervalli devono essere partizionati tra i thread mediante un algoritmo parallelo. Come illustrato in precedenza in questo documento, nella libreria PPL viene utilizzato un meccanismo di partizionamento predefinito tramite cui viene creato un carico di lavoro iniziale e, successivamente, utilizzato un algoritmo di acquisizione del lavoro e uno di acquisizione dell'intervallo per bilanciare queste partizioni quando i carichi di lavoro non lo sono. Ad esempio, quando tramite un'iterazione del ciclo viene completato un intervallo di iterazioni, il lavoro di altri thread viene ridistribuito a questo thread mediante il runtime. Tuttavia, per alcuni scenari, potrebbe essere necessario specificare un meccanismo di partizionamento differente, più adatto al problema.

Tramite gli algoritmi parallel_for, parallel_for_each e parallel_transform vengono fornite le versioni sottoposte a overload che accettano un parametro aggiuntivo, _Partitioner. Tramite questo parametro viene definito il tipo di partitioner che consente la divisione del lavoro. Di seguito sono riportati i tipi di partitioner definiti dalla libreria PPL:

Concurrency::affinity_partitioner
Il lavoro viene diviso in un numero fisso di intervalli (in genere il numero di thread di lavoro disponibili per il ciclo). Questo tipo di partitioner assomiglia a static_partitioner, tuttavia l'affinità della cache viene migliorata per quanto riguarda il mapping degli intervalli ai thread di lavoro. Questo tipo di partitioner può consentire il miglioramento delle prestazioni quando un ciclo viene eseguito più volte nello stesso set di dati (ad esempio un ciclo all'interno di un altro) e i dati sono adatti alla cache. Questo partitioner non è coinvolto completamente nell'annullamento. Inoltre non viene utilizzata la semantica di blocco cooperativo e, pertanto, non può essere utilizzato con cicli paralleli che hanno una dipendenza di inoltro.

Concurrency::auto_partitioner
Il lavoro viene diviso in un numero iniziale di intervalli (in genere il numero di thread di lavoro disponibili nel ciclo). Questo tipo viene utilizzato per impostazione predefinita dal runtime quando non viene chiamato un algoritmo parallelo sottoposto a overload che accetta un parametro _Partitioner. Ogni intervallo può essere suddiviso in intervalli secondari consentendo il bilanciamento del carico. Al termine di un intervallo di lavoro, gli intervalli di lavoro secondari vengo ridistribuiti da altri thread a questo tramite il runtime. Utilizzare questo partitioner se il carico di lavoro non rientra in una delle altre categorie o se è necessario un supporto completo per l'annullamento o il blocco cooperativo.

Concurrency::simple_partitioner
Il lavoro viene diviso in intervalli in modo che in ogni intervallo sia disponibile almeno il numero di iterazioni specificate dalla dimensione del blocco fornita. Questo tipo di partitioner è coinvolto nel bilanciamento del carico; tuttavia, gli intervalli non vengono suddivisi in intervalli secondari tramite il runtime. Per ogni thread di lavoro, tramite il runtime viene controllato l'annullamento e viene eseguito il bilanciamento del carico al termine delle iterazioni _Chunk_size.

Concurrency::static_partitioner
Il lavoro viene diviso in un numero fisso di intervalli (in genere il numero di thread di lavoro disponibili per il ciclo). Le prestazioni possono migliorare grazie a questo tipo di partitioner poiché non viene utilizzata l'acquisizione del lavoro e pertanto il sovraccarico è inferiore. Utilizzare questo tipo di partitioner quando tramite ogni iterazione di un ciclo parallelo viene eseguita una quantità di lavoro fissa e uniforme e non è richiesto supporto per l'annullamento o l'inoltro del blocco cooperativo.

System_CAPS_ICON_warning.jpg Avviso

Il parallel_for_each e parallel_transform algoritmi supportano solo i contenitori in cui vengono utilizzati iteratori ad accesso casuale (ad esempio std::vettore) per i partitioner statico, semplice e di affinità. Se si utilizzano contenitori con iteratori bidirezionali e di inoltro viene generato un errore in fase di compilazione. Il partitioner predefinito, auto_partitioner, supporta tutti e tre i tipi di iteratore.

In genere, questi partitioner vengono utilizzati nello stesso modo, ad eccezione di affinity_partitioner. La maggior parte dei tipi di partitioner non mantiene lo stato e non viene modificata dal runtime. Di conseguenza è possibile creare questi oggetti partitioner a livello del sito di chiamata, come illustrato nell'esempio seguente.

// static-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>

using namespace concurrency;

void DoWork(int n)
{
    // TODO: Perform a fixed amount of work...
}

int wmain()
{
    // Use a static partitioner to perform a fixed amount of parallel work.
    parallel_for(0, 100000, [](int n) {
        DoWork(n);
    }, static_partitioner());
}

Tuttavia, è necessario passare un oggetto affinity_partitioner come riferimento di valore l-value non const in modo che tramite l'algoritmo sia possibile archiviare lo stato per poterlo riutilizzare nei cicli futuri. Nell'esempio seguente viene mostrata un'applicazione di base tramite cui viene eseguita, più volte, la stessa operazione in un set di dati in parallelo. L'utilizzo di affinity_partitioner può migliorare le prestazioni poiché la matrice è probabilmente adatta alla cache.

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create an array and fill it with zeroes.
    array<unsigned char, 8 * 1024> data;
    data.fill(0);

    // Use an affinity partitioner to perform parallel work on data
    // that is likely to remain in cache.
    // We use the same affinitiy partitioner throughout so that the 
    // runtime can schedule work to occur at the same location for each 
    // iteration of the outer loop.

    affinity_partitioner ap;
    for (int i = 0; i < 100000; i++)
    {
        parallel_for_each(begin(data), end(data), [](unsigned char& c)
        {
            c++;
        }, ap);
    }
}

System_CAPS_ICON_caution.jpg Attenzione

Prestare attenzione quando si modifica il codice esistente basato sulla semantica di blocco cooperativo per utilizzare static_partitioner o affinity_partitioner. In questi tipi di partitioner non viene utilizzato il bilanciamento del carico o l'acquisizione dell'intervallo, quindi è possibile che il comportamento dell'applicazione venga modificato.

Il modo migliore per stabilire se è opportuno utilizzare un partitioner in qualsiasi scenario specificato consiste nello sperimentare e misurare il tempo necessario per il completamento delle operazioni con carichi e configurazioni di computer rappresentativi. Ad esempio, il partizionamento statico potrebbe fornire aumento di velocità significativo in un computer multicore con solo pochi core, ma potrebbe comportare rallentamenti nei computer che dispongono di core relativamente elevato.

[Torna all'inizio]

La libreria PPL fornisce tre algoritmi di ordinamento: Concurrency:: parallel_sort, Concurrency:: parallel_buffered_sort, e Concurrency:: parallel_radixsort. Questi algoritmi sono utili quando si dispone di un set di dati per cui l'ordinamento in parallelo risulta vantaggioso. In particolare, l'ordinamento in parallelo è utile in caso di un set di dati di grandi dimensioni o quando, per ordinare i dati, si utilizza un'operazione di confronto dispendiosa dal punto di vista del calcolo. Ognuno di questi algoritmi consente l'ordinamento degli elementi sul posto.

Gli algoritmi parallel_sort e parallel_buffered_sort sono entrambi basati sul confronto, cioè gli elementi vengono confrontati in base al valore. L'algoritmo parallel_sort non presenta requisiti di memoria aggiuntivi ed è appropriato per un ordinamento di utilizzo generale. Il parallel_buffered_sort può eseguire l'algoritmo migliore parallel_sort, ma richiede spazio o (n).

L'algoritmo parallel_radixsort è basato sull'hash, cioè vengono utilizzate chiavi di interi per ordinare gli elementi. Utilizzando le chiavi, tramite questo algoritmo può essere calcolata direttamente la destinazione di un elemento anziché ricorrere ai confronti. Ad esempio parallel_buffered_sort, questo algoritmo richiede spazio o (n).

Nella tabella seguente sono riepilogate le proprietà importanti dei tre algoritmi di ordinamento parallelo.

AlgoritmoDescrizioneMeccanismo di ordinamentoStabilità di ordinamentoRequisiti di memoriaComplessità di tempoAccesso iteratore
parallel_sortOrdinamento basato sul confronto per utilizzo generale.Basato sul confronto (crescente)InstabileNessunoO((N/P)log(N/P) + 2N((P-1)/P))Random
parallel_buffered_sortOrdinamento più veloce basato sul confronto per utilizzo generale per cui è richiesto lo spazio O(N).Basato sul confronto (crescente)InstabileÈ necessario ulteriore spazio o (n)O((N/P)log(N))Random
parallel_radixsortOrdinamento basato su chiave di interi per cui è richiesto lo spazio O(N).Basato su hashStableÈ necessario ulteriore spazio o (n)O(N/P)Random

Nella figura seguente vengono mostrate graficamente le proprietà importanti dei tre algoritmi di ordinamento paralleli.

Confronto degli algoritmi di ordinamento

Per questi algoritmi di ordinamento parallelo sono valide le regole di gestione dell'annullamento e delle eccezioni. Per ulteriori informazioni sull'annullamento e la gestione delle eccezioni nel Runtime di concorrenza, vedere annullamento degli algoritmi paralleli e Exception Handling.

System_CAPS_ICON_tip.jpg Suggerimento

Questi algoritmi di ordinamento parallelo supportano la semantica di spostamento. È possibile definire un operatore di assegnazione di spostamento per migliorare l'efficienza delle operazioni di scambio. Per ulteriori informazioni sulla semantica di spostamento e l'operatore di assegnazione di spostamento, vedere dichiaratore di riferimento Rvalue: & &, e spostare i costruttori e operatori di assegnazione di spostamento (C++). Se non viene fornito un operatore di assegnazione di spostamento o una funzione di scambio, negli algoritmi di ordinamento viene utilizzato il costruttore di copia.

Nell'esempio di base seguente viene illustrato come utilizzare parallel_sort per ordinare un vector di valori int. Per impostazione predefinita, parallel_sort utilizza std:: less per confrontare i valori.

// basic-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create and sort a large vector of random values.
    vector<int> values(25000000);
    generate(begin(values), end(values), mt19937(42));
    parallel_sort(begin(values), end(values));

    // Print a few values.
    wcout << "V(0)        = " << values[0] << endl;
    wcout << "V(12500000) = " << values[12500000] << endl;
    wcout << "V(24999999) = " << values[24999999] << endl;
} 
/* Output:
   V(0)        = -2147483129
   V(12500000) = -427327
   V(24999999) = 2147483311
*/

In questo esempio viene illustrato come fornire una funzione di confronto personalizzata. Usa il std::complex::real metodo per ordinare std:: Complex < double> valori in ordine crescente.

    // For this example, ensure that you add the following #include directive:
    // #include <complex>

    // Create and sort a large vector of random values.
    vector<complex<double>> values(25000000);
    generate(begin(values), end(values), mt19937(42));
    parallel_sort(begin(values), end(values),
        [](const complex<double>& left, const complex<double>& right) {
            return left.real() < right.real();
        });

    // Print a few values.
    wcout << "V(0)        = " << values[0] << endl;
    wcout << "V(12500000) = " << values[12500000] << endl;
    wcout << "V(24999999) = " << values[24999999] << endl;
    /* Output:
       V(0)        = (383,0)
       V(12500000) = (2.1479e+009,0)
       V(24999999) = (4.29497e+009,0)
    */

In questo esempio viene illustrato come fornire una funzione hash all'algoritmo parallel_radixsort. In questo esempio vengono ordinati i punti 3D. I punti vengono ordinati in base alla distanza da un punto di riferimento.

// parallel-sort-points.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

// Defines a 3-D point.
struct Point
{
    int X;
    int Y;
    int Z;
};

// Computes the Euclidean distance between two points.
size_t euclidean_distance(const Point& p1, const Point& p2)
{
    int dx = p1.X - p2.X;
    int dy = p1.Y - p2.Y;
    int dz = p1.Z - p2.Z;
    return static_cast<size_t>(sqrt((dx*dx) + (dy*dy) + (dz*dz)));
}

int wmain()
{
    // The central point of reference.
    const Point center = { 3, 2, 7 };

    // Create a few random Point values.
    vector<Point> values(7);
    mt19937 random(42);
    generate(begin(values), end(values), [&random] {
        Point p = { random()%10, random()%10, random()%10 };
        return p;
    });

    // Print the values before sorting them.
    wcout << "Before sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;

    // Sort the values based on their distances from the reference point.
    parallel_radixsort(begin(values), end(values), 
        [center](const Point& p) -> size_t {
            return euclidean_distance(p, center);
        });

    // Print the values after sorting them.
    wcout << "After sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;
} 
/* Output:
    Before sorting:
    (2,7,6) D = 5
    (4,6,5) D = 4
    (0,4,0) D = 7
    (3,8,4) D = 6
    (0,4,1) D = 7
    (2,5,5) D = 3
    (7,6,9) D = 6

    After sorting:
    (2,5,5) D = 3
    (4,6,5) D = 4
    (2,7,6) D = 5
    (3,8,4) D = 6
    (7,6,9) D = 6
    (0,4,0) D = 7
    (0,4,1) D = 7
*/

A titolo esemplificativo, in questo esempio viene utilizzato un set di dati relativamente piccolo. È possibile aumentare la dimensione iniziale del vettore per sperimentare miglioramenti delle prestazioni in set di dati di grandi dimensioni.

In questo esempio viene utilizzata un'espressione lambda come funzione hash. È inoltre possibile utilizzare una delle implementazioni predefinite di std::classe hash o definirne una personalizzata. È anche possibile utilizzare un oggetto della funzione hash personalizzato, come illustrato in questo esempio:

// Functor class for computing the distance between points.
class hash_distance
{
public:
    hash_distance(const Point& reference)
        : m_reference(reference)
    {
    }

    size_t operator()(const Point& pt) const {
        return euclidean_distance(pt, m_reference);
    }

private:
    Point m_reference;
};

    // Use hash_distance to compute the distance between points.
    parallel_radixsort(begin(values), end(values), hash_distance(center));

La funzione hash deve restituire un tipo integrale (std::is_integral::value deve essere true). Questo tipo integrale deve poter essere convertito nel tipo size_t.

Scelta di un algoritmo di ordinamento

In molti casi, tramite parallel_sort viene fornito il migliore bilanciamento delle prestazioni di memoria e velocità. Tuttavia, quando si aumenta la dimensione del set di dati, il numero di processori disponibili o la complessità della funzione di confronto, parallel_buffered_sort o parallel_radixsort può risultare più efficace. Il modo migliore per stabilire quale algoritmo di ordinamento utilizzare in qualsiasi scenario specificato consiste nello sperimentare e misurare il tempo necessario per ordinare dati tipici con configurazioni di computer rappresentativi. Tenere presenti le linee guida seguenti quando si sceglie una strategia di ordinamento.

  • La dimensione del set di dati. In questo documento, un small set di dati contiene meno di 1.000 elementi, un Media inclusi tra 10.000 e 100.000 elementi e un grandi set di dati contiene più di 100.000 elementi.

  • La quantità di lavoro eseguita dalla funzione di confronto o dalla funzione hash.

  • La quantità di risorse di elaborazione disponibili.

  • Le caratteristiche del set di dati. Ad esempio, il funzionamento di un algoritmo può essere ottimo per i dati che sono già quasi ordinati, ma non altrettanto valido per i dati che non sono ordinati.

  • La dimensione del blocco. Nell'argomento _Chunk_size facoltativo viene specificato quando l'algoritmo passa da un'implementazione di ordinamento parallela a una seriale mentre l'ordinamento complessivo viene suddiviso in unità di lavoro più piccole. Ad esempio, se si fornisce 512, l'algoritmo passa a un'implementazione seriale quando in un'unità di lavoro sono contenuti al massimo 512 elementi. Con un'implementazione seriale le prestazioni complessive possono migliorare poiché viene eliminato il sovraccarico richiesto per elaborare i dati in parallelo.

Potrebbe non essere utile effettuare l'ordinamento di un piccolo set di dati in parallelo, anche quando si dispone di molte risorse di elaborazione o quando tramite la funzione hash o di confronto viene eseguita una quantità di lavoro relativamente grande. È possibile utilizzare std:: Sort funzione per ordinare i set di dati piccoli. (parallel_sort e parallel_buffered_sort chiamare sort quando si specifica una dimensione del blocco è maggiore di set di dati; tuttavia, parallel_buffered_sort potrebbe essere necessario allocare spazio o (n), che può richiedere più tempo a causa di blocco dell'allocazione di memoria o di contesa.)

Se è necessario ridurre l'utilizzo di memoria o se l'allocatore di memoria è soggetto ai conflitti di blocco, utilizzare parallel_sort per ordinare un set di dati di medie dimensioni. parallel_sort è richiesto alcun spazio aggiuntivo; gli altri algoritmi è richiesto spazio o (n).

Utilizzare parallel_buffered_sort per ordinare i set di dati di medie dimensioni e quando l'applicazione soddisfa i requisiti di spazio aggiuntivo o (n). parallel_buffered_sort può essere particolarmente utile quando si dispone di molte risorse di elaborazione oppure di una funzione hash o di confronto dispendiosa.

Utilizzare parallel_radixsort per ordinare i set di dati di grandi dimensioni e quando l'applicazione soddisfa i requisiti di spazio aggiuntivo o (n). parallel_radixsort può essere particolarmente utile quando l'operazione di confronto equivalente è più dispendiosa o quando entrambe le operazioni sono dispendiose.

System_CAPS_ICON_caution.jpg Attenzione

Per l'implementazione di una funzione hash valida è necessario conoscere l'intervallo del set di dati e il modo in cui ogni elemento nel set di dati viene trasformato in un valore unsigned corrispondente. Poiché per l'operazione hash vengono utilizzati valori unsigned, prendere in considerazione una strategia di ordinamento diversa se non è possibile generare valori hash unsigned.

Nell'esempio seguente vengono confrontate le prestazioni di sort, parallel_sort, parallel_buffered_sort e parallel_radixsort in set di dati casuali di uguale dimensione.

// choosing-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
#include <windows.h>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

const size_t DATASET_SIZE = 10000000;

// Create
// Creates the dataset for this example. Each call
// produces the same predefined sequence of random data.
vector<size_t> GetData()
{
    vector<size_t> data(DATASET_SIZE);
    generate(begin(data), end(data), mt19937(42));
    return data;
}

int wmain()
{
    // Use std::sort to sort the data.
    auto data = GetData();
    wcout << L"Testing std::sort...";
    auto elapsed = time_call([&data] { sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_sort...";
    elapsed = time_call([&data] { parallel_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_buffered_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_buffered_sort...";
    elapsed = time_call([&data] { parallel_buffered_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_radixsort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_radixsort...";
    elapsed = time_call([&data] { parallel_radixsort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;
} 
/* Sample output (on a computer that has four cores):
    Testing std::sort... took 2906 ms.
    Testing concurrency::parallel_sort... took 2234 ms.
    Testing concurrency::parallel_buffered_sort... took 1782 ms.
    Testing concurrency::parallel_radixsort... took 907 ms.
*/

In questo esempio, che presuppone che sia accettabile per allocare spazio o (n) durante l'ordinamento, parallel_radixsort risulta più efficiente in questo set di dati in questa configurazione del computer.

[Torna all'inizio]

TitoloDescrizione
Procedura: scrivere un ciclo parallel_forViene illustrato come utilizzare il parallel_for algoritmo per eseguire la moltiplicazione.
Procedura: scrivere un ciclo parallel_for_eachViene illustrato come utilizzare il parallel_for_each algoritmo per calcolare il conteggio dei numeri primi in un std:: Array oggetto in parallelo.
Procedura: utilizzare parallel_invoke per scrivere una Routine di ordinamento paralleloViene illustrato come usare l'algoritmo parallel_invoke per migliorare le prestazioni dell'algoritmo di ordinamento bitonico.
Procedura: utilizzare parallel_invoke per eseguire operazioni in paralleloViene illustrato come usare l'algoritmo parallel_invoke per migliorare le prestazioni di un programma che esegue più operazioni in un'origine dati condivisa.
Procedura: eseguire mapping e riduzione delle operazioni in paralleloViene mostrato come utilizzare gli algoritmi parallel_transform e parallel_reduce per eseguire un'operazione di mapping e di riduzione tramite cui vengono contate le occorrenze di parole nei file.
Parallel Patterns Library (PPL)Viene descritta la libreria PPL, che fornisce un modello di programmazione imperativa in grado di offrire scalabilità e facilità di utilizzo per lo sviluppo di applicazioni simultanee.
AnnullamentoViene illustrato il ruolo dell'annullamento nella libreria PPL, come annullare un lavoro parallelo e come determinare quando un gruppo di attività viene annullato.
Gestione delle eccezioniViene illustrato il ruolo di gestione delle eccezioni nel Runtime di concorrenza.

Funzione parallel_for

Funzione parallel_for_each

Funzione parallel_invoke

Classe affinity_partitioner

auto_partitioner (classe)

Classe simple_partitioner

Classe static_partitioner

parallel_sort (funzione)

Funzione parallel_buffered_sort

Funzione parallel_radixsort

Mostra: