Algoritmi paralleli

La libreria PPL (Parallel Patterns Library) fornisce algoritmi che eseguono simultaneamente operazioni sulle raccolte di dati. Questi algoritmi sono simili a quelli forniti dalla libreria standard C++.

Gli algoritmi paralleli sono costituiti da funzionalità esistenti nel runtime di concorrenza. Ad esempio, l'algoritmo concurrency::p arallel_for usa un oggetto concurrency::structured_task_group per eseguire le iterazioni del ciclo parallelo. Le partizioni dell'algoritmo parallel_for funzionano in modo ottimale in base al numero disponibile di risorse di calcolo.

Sezioni

• Algoritmo parallel_for

• Algoritmo parallel_for_each

• Algoritmo parallel_invoke

• Algoritmi parallel_transform e parallel_reduce

  • Algoritmo parallel_transform

  • Algoritmo parallel_reduce

  • Esempio: esecuzione di mapping e riduzione in parallelo

• Lavoro di partizionamento

• Ordinamento parallelo

  • Scelta di un algoritmo di ordinamento

Algoritmo parallel_for

L'algoritmo concurrency::p arallel_for esegue ripetutamente la stessa attività in parallelo. Ognuna di queste attività è parametrizzata da un valore di iterazione. Questo algoritmo è utile quando si dispone di un corpo del ciclo che non condivide le risorse tra le iterazioni del ciclo.

L'algoritmo parallel_for partiziona 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 si blocca in modo cooperativo, il runtime ridistribuisce l'intervallo di iterazioni assegnate al thread corrente ad altri thread o processori. Analogamente, quando un thread completa un intervallo di iterazioni, il runtime ridistribuisce il lavoro da altri thread a tale thread. L'algoritmo parallel_for supporta anche il parallelismo annidato. Quando un ciclo parallelo contiene un altro ciclo parallelo, il runtime coordina le risorse di elaborazione tra i corpi del 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 di lavoro (espressione lambda, oggetto funzione o puntatore a funzione). La seconda versione accetta un valore iniziale, un valore finale, un valore in base al quale eseguire il passaggio e una funzione di lavoro. La prima versione di questa funzione usa 1 come valore del passaggio. 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 partizionatori sono illustrati in modo più dettagliato nella sezione Partizionamento del lavoro in questo documento.

È possibile convertire molti for cicli per usare parallel_for. Tuttavia, l'algoritmo parallel_for differisce dall'istruzione for nei modi seguenti:

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

• L'algoritmo parallel_for non supporta condizioni di terminazione arbitrarie. L'algoritmo parallel_for si arresta quando il valore corrente della variabile di iterazione è minore di last.

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

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

• Il meccanismo di gestione delle eccezioni per l'algoritmo parallel_for è 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 al thread che ha chiamato parallel_for. Inoltre, quando un'iterazione del ciclo genera un'eccezione, il runtime non arresta immediatamente il ciclo complessivo. Il ciclo viene invece inserito nello stato annullato e il runtime rimuove tutte le attività che non sono ancora state avviate. Per altre informazioni sulla gestione delle eccezioni e sugli algoritmi paralleli, vedere Gestione delle eccezioni.

Anche se l'algoritmo parallel_for non supporta condizioni di terminazione arbitrarie, è possibile usare l'annullamento per arrestare tutte le attività. Per altre informazioni sull'annullamento, vedere Annullamento in PPL.

Nota

Il costo di pianificazione risultante dal bilanciamento del carico e dal supporto per funzionalità come l'annullamento potrebbe 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 altre informazioni, vedere Partizionamento del lavoro più avanti in questo documento.

Esempio

Nell'esempio seguente viene illustrata la struttura di base dell'algoritmo parallel_for . In questo esempio viene stampato nella console ogni 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 l'output di esempio seguente:

1 2 4 3 5

Poiché l'algoritmo parallel_for agisce su ogni elemento in parallelo, l'ordine in cui i valori vengono stampati nella console varia.

Per un esempio completo che usa l'algoritmo parallel_for , vedere Procedura: Scrivere un ciclo parallel_for.

[Torna all'inizio]

Algoritmo parallel_for_each

L'algoritmo concurrency::p arallel_for_each esegue attività su un contenitore iterativo, ad esempio quelli forniti dalla libreria standard C++, in parallelo. Usa la stessa logica di partizionamento usata dall'algoritmo parallel_for .

L'algoritmo parallel_for_each è simile all'algoritmo std::for_each della libreria standard C++, ad eccezione del fatto che l'algoritmo parallel_for_each esegue le attività contemporaneamente. Analogamente ad altri algoritmi paralleli, parallel_for_each non esegue le attività in un ordine specifico.

Sebbene l'algoritmo parallel_for_each funzioni sia su iteratori in avanti che su iteratori ad accesso casuale, offre prestazioni migliori con iteratori ad accesso casuale.

Esempio

Nell'esempio seguente viene illustrata la struttura di base dell'algoritmo parallel_for_each . In questo esempio viene stampato nella console ogni valore in un oggetto std::array 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 l'output di esempio seguente:

4 5 1 2 3

Poiché l'algoritmo parallel_for_each agisce su ogni elemento in parallelo, l'ordine in cui i valori vengono stampati nella console varia.

Per un esempio completo che usa l'algoritmo parallel_for_each , vedere Procedura: Scrivere un ciclo parallel_for_each.

[Torna all'inizio]

Algoritmo parallel_invoke

L'algoritmo concurrency::p arallel_invoke esegue un set di attività in parallelo. Non viene restituito fino al termine di ogni attività. Questo algoritmo è utile quando si hanno diverse attività indipendenti da eseguire contemporaneamente.

L'algoritmo parallel_invoke accetta come parametri una serie di funzioni di lavoro (funzioni lambda, oggetti funzione o puntatori a funzione). L'algoritmo parallel_invoke è sottoposto a overload per accettare tra due e dieci parametri. Ogni funzione passata a deve accettare parallel_invoke zero parametri.

Analogamente ad altri algoritmi paralleli, parallel_invoke non esegue le attività in un ordine specifico. L'argomento Parallelismo attività illustra in che modo l'algoritmo parallel_invoke è correlato alle attività e ai gruppi di attività.

Esempio

Nell'esempio seguente viene illustrata la struttura di base dell'algoritmo parallel_invoke . Questo esempio chiama contemporaneamente la twice funzione su tre variabili locali e stampa 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;
}

Nell'esempio viene prodotto l'output seguente:

108 11.2 HelloHello

Per esempi completi che usano l'algoritmo parallel_invoke , vedere Procedura: Usare parallel_invoke per scrivere una routine di ordinamento parallelo e Procedura: Usare parallel_invoke per eseguire operazioni parallele.

[Torna all'inizio]

Algoritmi parallel_transform e parallel_reduce

Gli algoritmi concurrency::p arallel_transform e concurrency::p arallel_reduce sono versioni parallele degli algoritmi della libreria standard C++ std::transform e std::accumulate, rispettivamente. Le versioni del runtime di concorrenza si comportano come le versioni della libreria standard C++, ad eccezione del fatto che l'ordine dell'operazione non viene determinato perché 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.

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.

Algoritmo parallel_transform

È possibile utilizzare l'algoritmo parallel transform per eseguire molte operazioni di parallelizzazione dati. È ad esempio possibile:

• 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 nega ogni elemento di un oggetto std::vector in due modi. Nel primo viene utilizzata un'espressione lambda. Il secondo modo usa 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>());
}

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>());

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.

Algoritmo parallel_reduce

L'algoritmo parallel_reduce è utile quando si dispone di una sequenza di operazioni che soddisfano la proprietà associativa; Questo algoritmo non richiede la proprietà commutativa. Ecco 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{
      L"Lorem ",
      L"ipsum ",
      L"dolor ",
      L"sit ",
      L"amet, ",
      L"consectetur ",
      L"adipiscing ",
      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 considerare parallel_reduce come abbreviato per l'uso dell'algoritmo parallel_for_each insieme alla classe concurrency::combinable .

Esempio: esecuzione di mapping e riduzione in parallelo

Un'operazione di mapping applica una funzione a ogni valore in una sequenza. Un'operazione di riduzione combina gli elementi di una sequenza in un unico valore. È possibile usare le funzioni std::transform e std::accumulate della libreria standard C++ per eseguire operazioni di mapping e riduzione. 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 un'operazione di mapping e riduzione in parallelo, vedere Procedura: Eseguire operazioni di mapping e riduzione in parallelo.

[Torna all'inizio]

Lavoro di partizionamento

Per parallelizzare un'operazione su un'origine dati, un passaggio essenziale consiste nel partizionare l'origine in più sezioni a cui è possibile accedere simultaneamente 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.

Avviso

Gli parallel_for_each algoritmi e parallel_transform supportano solo i contenitori che usano iteratori ad accesso casuale (ad esempio std::vector) per i partitioner statici, semplici 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);
    }
}

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. Il partizionamento statico, ad esempio, potrebbe offrire un considerevole aumento di velocità in un computer con solo pochi core, ma potrebbe comportare rallentamenti nei computer con un numero relativamente elevato di core.

[Torna all'inizio]

Ordinamento parallelo

Il PPL fornisce tre algoritmi di ordinamento: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort e concurrency::p arallel_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. L'algoritmo parallel_buffered_sort può ottenere prestazioni migliori rispetto parallel_sorta , 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. Come parallel_buffered_sort, questo algoritmo richiede spazio O(N).

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

Algoritmo	Descrizione	Meccanismo di ordinamento	Stabilità di ordinamento	Requisiti di memoria	Complessità di tempo	Accesso iteratore
parallel_sort	Ordinamento basato sul confronto per utilizzo generale.	Basato sul confronto (crescente)	Instabile	None	O((N/P)log(N/P) + 2N((P-1)/P))	Casuale
parallel_buffered_sort	Ordinamento più veloce basato sul confronto per utilizzo generale per cui è richiesto lo spazio O(N).	Basato sul confronto (crescente)	Instabile	Richiede spazio O(N) aggiuntivo	O((N/P)log(N))	Casuale
parallel_radixsort	Ordinamento basato su chiave di interi per cui è richiesto lo spazio O(N).	Basato su hash	Stable	Richiede spazio O(N) aggiuntivo	O(N/P)	Casuale

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

Per questi algoritmi di ordinamento parallelo sono valide le regole di gestione dell'annullamento e delle eccezioni. Per altre informazioni sulla gestione degli annullamenti e delle eccezioni nel runtime di concorrenza, vedere Annullamento di algoritmi paralleli e gestione delle eccezioni.

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 altre informazioni sulla semantica di spostamento e sull'operatore di assegnazione di spostamento, vedere Rvalue Reference Declarator: &&, and Move Constructors and Move Assignment Operators (C++).For more information about move semantics and the move assignment operator, see Rvalue Reference Declarator: &&, and Move Constructors and Move Assignment Operators (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 usa 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 metodo std::complex::real per ordinare i valori double> std::complex<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. È anche possibile usare una delle implementazioni predefinite della classe std::hash o definire la propria specializzazione. È 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 set di dati di piccole dimensioni contiene meno di 1.000 elementi, un set di dati medio contiene tra 10.000 e 100.000 elementi e un set di dati di grandi dimensioni 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 usare la funzione std::sort per ordinare set di dati di piccole dimensioni. (parallel_sort e parallel_buffered_sort chiamare sort quando si specifica una dimensione di blocco maggiore del set di dati; tuttavia, parallel_buffered_sort sarebbe necessario allocare spazio O(N), che potrebbe richiedere tempo aggiuntivo a causa della contesa di blocco o dell'allocazione di memoria.

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 non richiede spazio aggiuntivo; gli altri algoritmi richiedono spazio O(N).

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

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

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 allocare spazio O(N) durante l'ordinamento, parallel_radixsort esegue le prestazioni migliori in questo set di dati in questa configurazione del computer.

[Torna all'inizio]

Argomenti correlati

Posizione	Descrizione
Procedura: Scrivere un ciclo parallel_for	Illustra come usare l'algoritmo per eseguire la parallel_for moltiplicazione di matrici.
Procedura: Scrivere un ciclo parallel_for_each	Illustra come usare l'algoritmo parallel_for_each per calcolare il conteggio dei numeri primi in un oggetto std::array in parallelo.
Procedura: Usare parallel_invoke per scrivere una routine di ordinamento in parallelo	Viene illustrato come usare l'algoritmo parallel_invoke per migliorare le prestazioni dell'algoritmo di ordinamento bitonico.
Procedura: Usare parallel_invoke per eseguire operazioni in parallelo	Viene 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 operazioni di mapping e riduzione in parallelo	Viene 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.
PPL (Parallel Patterns Library)	Descrive il PPL, che fornisce un modello di programmazione imperativo che promuove scalabilità e facilità d'uso per lo sviluppo di applicazioni simultanee.
Annullamento nella libreria PPL	Illustra il ruolo di annullamento nel PPL, come annullare il lavoro parallelo e come determinare quando un gruppo di attività viene annullato.
Gestione delle eccezioni	Illustra il ruolo della gestione delle eccezioni nel runtime di concorrenza.

Riferimento

Funzione parallel_for

Funzione parallel_for_each

Funzione parallel_invoke

Classe affinity_partitioner

Classe auto_partitioner

Classe simple_partitioner

Classe static_partitioner

Funzione parallel_sort

Funzione parallel_buffered_sort

Funzione parallel_radixsort