Algoritmi paralleli
La libreria PPL (Parallel Patterns Library) fornisce gli algoritmi per svolgere simultaneamente il lavoro sulle raccolte di dati. Questi algoritmi sono simili a quelli forniti dalla libreria STL (Standard Template Library).
Gli algoritmi paralleli sono costituiti da funzionalità esistenti nel runtime di concorrenza. L'algoritmo concurrency::parallel_for utilizza, ad esempio, un oggetto concurrency::structured_task_group per eseguire le iterazioni del ciclo parallelo. L'algoritmo parallel_for partiziona il lavoro in modo ottimale in base al numero di risorse di elaborazione disponibili.
Sezioni
L'algoritmo parallel_for
L'algoritmo parallel_for_each
L'algoritmo parallel_invoke
Gli algoritmi parallel_reduce e parallel_transform
L'algoritmo parallel_transform
L'algoritmo parallel_reduce
Esempio: esecuzione del mapping e riduzione in parallelo
Suddivisione del lavoro
Ordinamento parallelo
- Scelta di un algoritmo di ordinamento
L'algoritmo parallel_for
L'algoritmo concurrency::parallel_for esegue ripetutamente la stessa attività in parallelo. Ognuna di queste attività contiene i parametri per un valore dell'iterazione. Questo algoritmo è utile quando è presente 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 in parallelo. Utilizza 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 delle iterazioni assegnato al thread corrente agli altri thread o processori. In modo analogo, quando un thread completa un intervallo di iterazioni, il runtime ridistribuisce il lavoro degli 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.
L'algoritmo parallel_for dispone di alcune versioni di overload. La prima versione accetta un valore iniziale, un valore finale e una funzione lavoro, ovvero un'espressione lambda, un oggetto funzione o un puntatore a funzione. La seconda versione accetta un valore iniziale, un valore finale, un valore di incremento 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 come la modalità parallel_for deve partizionare per intervalli tra thread. I partitioner sono descritti più dettagliatamente nella sezione Suddivisione lavoro in questo documento.
È possibile convertire molti cicli for affinché venga utilizzato parallel_for. Tuttavia, tra l'algoritmo parallel_for e l'istruzione for esistono le differenze seguenti:
L'algoritmo parallel_for non esegue le attività in un ordine predeterminato.
L'algoritmo parallel_for non supporta condizioni di terminazione arbitraria. L'algoritmo parallel_for si arresta quando il valore corrente della variabile di iterazione è inferiore di un'unità rispetto a _Last.
Il parametro di tipo _Index_type deve essere un tipo integrale. Questo tipo integrale può essere con segno o senza segno.
L'iterazione del ciclo deve essere in avanti. L'algoritmo parallel_for genera un'eccezione di tipo std::invalid_argument se il parametro _Step è minore di 1.
Il meccanismo di gestione delle eccezioni per l'algoritmo parallel_for differisce da quello di un ciclo for. Se si verificano più eccezioni contemporaneamente nel corpo di un ciclo parallelo, il runtime propaga solo una delle eccezioni nel thread che ha chiamato parallel_for. Inoltre, quando un'iterazione del ciclo genera un'eccezione, il runtime non interrompe immediatamente il ciclo globale. Il ciclo passa invece allo stato annullato e il runtime rimuove tutte le attività che non sono ancora state avviate. Per ulteriori informazioni sulla gestione delle eccezioni e sugli algoritmi paralleli, vedere Gestione delle eccezioni nel runtime di concorrenza.
Sebbene l'algoritmo parallel_for non supporti condizioni di terminazione arbitraria, è possibile utilizzare l'annullamento per arrestare tutte le attività. Per ulteriori informazioni sull'annullamento, vedere Annullamento nella libreria PPL.
Nota
È possibile che il costo di pianificazione che risulta dal bilanciamento del carico e il supporto di funzionalità come l'annullamento non superino i vantaggi dell'esecuzione del corpo del ciclo in parallelo, soprattutto quando il corpo del ciclo è relativamente piccolo.È possibile ridurre questo sovraccarico utilizzando un partitioner nel ciclo parallelo.Per ulteriori informazioni, vedere Suddivisione lavoro successivamente in questo documento.
Esempio
Nell'esempio seguente viene mostrata la struttura di base dell'algoritmo parallel_for. L'esempio visualizza 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 seguente:
Poiché l'algoritmo parallel_for agisce su ogni elemento in parallelo, l'ordine in cui vengono visualizzati i valori nella console sarà diverso.
Per un esempio completo in cui viene utilizzato l'algoritmo parallel_for, vedere Procedura: scrivere un ciclo parallel_for.
[Top]
L'algoritmo parallel_for_each
L'algoritmo concurrency::parallel_for_each esegue le attività su un contenitore iterativo, ad esempio quelli forniti dalla libreria STL, in parallelo. Utilizza la stessa logica di partizionamento utilizzata dall'algoritmo parallel_for.
L'algoritmo parallel_for_each è simile all'algoritmo std::for_each STL, con l'unica differenza che l'algoritmo parallel_for_each esegue le attività simultaneamente. Analogamente agli altri algoritmi paralleli, parallel_for_each non esegue le attività in un ordine specifico.
Sebbene l'algoritmo parallel_for_each possa essere utilizzato sia con gli iteratori in avanti che con gli iteratori di accesso casuale, le prestazioni sono migliori con gli iteratori di accesso casuale.
Esempio
Nell'esempio seguente viene mostrata la struttura di base dell'algoritmo parallel_for_each. L'esempio visualizza 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 seguente:
Poiché l'algoritmo parallel_for_each agisce su ogni elemento in parallelo, l'ordine in cui vengono visualizzati i valori nella console sarà diverso.
Per un esempio completo in cui viene utilizzato l'algoritmo parallel_for_each, vedere Procedura: scrivere un ciclo parallel_for_each.
[Top]
L'algoritmo parallel_invoke
L'algoritmo concurrency::parallel_invoke esegue un set di attività in parallelo. Non restituisce alcun valore finché non vengono completate tutte le attività. Questo algoritmo è utile quando si desidera eseguire contemporaneamente diverse attività indipendenti.
L'algoritmo parallel_invoke accetta come parametri una serie di funzioni lavoro, ovvero funzioni lambda, oggetti funzione o puntatori a funzione. Viene eseguito l'overload dell'algoritmo parallel_invoke per accettare da due a dieci parametri. Ogni funzione che si passa a parallel_invoke deve accettare zero parametri.
Analogamente agli altri algoritmi paralleli, parallel_invoke non esegue le attività in un ordine specifico. Nell'argomento Parallelismo delle attività (runtime di concorrenza) viene illustrato come l'algoritmo parallel_invoke viene correlato alle attività e ai gruppi di attività.
Esempio
Nell'esempio seguente viene mostrata la struttura di base dell'algoritmo parallel_invoke. In questo esempio viene chiamata la funzione twice contemporaneamente in tre variabili locali e viene visualizzato 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:
Per gli esempi completi in cui viene utilizzato l'algoritmo parallel_invoke, vedere Procedura: utilizzare parallel_invoke per scrivere una routine di ordinamento in parallelo e Procedura: utilizzare parallel_invoke per eseguire operazioni in parallelo.
[Top]
Gli algoritmi parallel_reduce e parallel_transform
Gli algoritmi concurrency::parallel_reduce e concurrency::parallel_transform sono versioni parallele degli algoritmi SLT std::transform e std::accumulate, rispettivamente. Le versioni del runtime di concorrenza si comportano come le versioni della libreria STL ma l'ordine delle operazioni non viene determinato in quanto vengono eseguite in parallelo. Utilizzare questi algoritmi quando si utilizzano con un set sufficientemente grande da ottenere vantaggi di scalabilità e di prestazioni dall'essere elaborati in parallelo.
Importante
Gli algoritmi parallel_reduce e parallel_transform supportano solo iteratori di accesso casuale, bidirezionale e di inoltro perché questi iteratori producono indirizzi di memoria stabile.Inoltre, questi iteratori devono produrre valori non-const.
L'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 ed eseguire altri calcoli numerici sui vettori.
Eseguire il tracciamento di raggio 3-D, in cui ogni iterazione fa riferimento ad un pixel sul quale deve essere eseguito il rendering.
L'esempio seguente mostra la struttura di base usata per chiamare l'algoritmo parallel_transform. Questo esempio nega ogni elemento di un oggetto std::vector in due modi. La prima modalità utilizza un'espressione lambda. La seconda modalità sfrutta 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
Questo esempio mostra l'utilizzo di base di parallel_transform.Poiché la funzione di lavoro non esegue una quantità significativa di lavoro, non è previsto un miglioramento significativo delle prestazioni in questo esempio.
L'algoritmo parallel_transform dispone di due overload. Il primo overload accetta un intervallo di input e una funzione unaria. La funzione unaria può essere un'espressione lambda che accetta un unico argomento, un oggetto funzione o un tipo che deriva da unary_function. Il secondo overload accetta due intervalli di input e una funzione binaria. La funzione binary può essere un'espressione lambda che accetta due argomenti, un oggetto funzione o un tipo che deriva da std::binary_function. L'esempio che segue illustra 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 sovrapposti 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 ha di una sequenza di operazioni che soddisfano la proprietà associativa. (Questo algoritmo non richiede la proprietà commutativa.) Di seguito sono elencate alcune delle operazioni eseguibili con parallel_reduce:
Moltiplicare sequenze di matrici per produrre una matrice.
Moltiplicare un vettore per una sequenza di matrici per produrre un vettore.
Calcola la lunghezza di una sequenza di stringhe.
Unire un elenco di elementi, quali stringhe, in un unico elemento.
L'esempio di base seguente mostra come utilizzare l'algoritmo parallel_reduce per combinare una sequenza di stringhe in un'unica stringa. Come negli esempi di parallel_transform, gli incrementi di 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, si può considerare parallel_reduce come un metodo sintetico per l'utilizzo dell'algoritmo parallel_for_each insieme alla classe concurrency::combinable.
Esempio: esecuzione del 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 valore. È possibile utilizzare le classi standard della libreria STL (Standard Template Library) std::transform e std::accumulate per eseguire le operazioni di mapping e di riduzione. Tuttavia, per molti problemi, è possibile utilizzare l'algoritmo parallel_transform per eseguire l'operazione di mappa in parallelo e l'algoritmo parallel_reduce per eseguire l'operazione di riduzione in parallelo.
L'esempio seguente confronta il tempo richiesto per calcolare la somma dei numeri primi in serie e in parallelo. La fase mappa pone i valori non-primi a 0 e la fase di riduzione somma i valori.
// 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 l'operazione di riduzione in parallelo, vedere Procedura: eseguire operazioni di mapping e riduzione in parallelo.
[Top]
Suddivisione del lavoro
Un passaggio basilare per la parallelizzazione di un'operazione su un'origine dati consiste nel suddividere l'origine in più sezioni, cui è possibile accedere contemporaneamente da più thread. Un partitioner specifica come un algoritmo parallelo deve partizionare gli intervalli tra i thread. Come illustrato in precedenza in questo documento, la libreria PPL utilizza un meccanismo di partizionamento predefinito che crea un carico di lavoro iniziale e quindi utilizza un algoritmo di acquisizione del lavoro e un algoritmo di acquisizione dell'intervallo per bilanciare queste partizioni quando i carichi di lavoro non sono bilanciati. Ad esempio, quando un'iterazione di loop completa un intervallo di iterazioni, il runtime ridistribuisce il lavoro degli altri thread a tale thread. Tuttavia, per alcuni scenari, è possibile specificare un meccanismo di partizionamento differente che è più adatto al problema.
Gli algoritmi parallel_for, parallel_for_each e parallel_transform forniscono le versioni di overload che accettano un parametro aggiuntivo, _Partitioner. Questo parametro definisce il tipo di partitioner che divide il lavoro. Di seguito sono illustrati i tipi di partitioner che la libreria PPL definisce:
concurrency::affinity_partitioner
Divide il lavoro in un numero fisso di intervalli (in genere il numero di thread di lavoro disponibili per lavorare con il ciclo). Questo tipo di partitioner assomiglia a static_partitioner, ma migliora l'affinità della cache nel modo in cui esegue il mapping degli intervalli ai thread di lavoro. Questo tipo di partitioner può migliorare le prestazioni mentre viene eseguito un ciclo sullo stesso set di dati più volte (ad esempio un ciclo all'interno di un ciclo) e i dati sono adatti alla cache. Questo partitioner non partecipa pienamente all'annullamento. Inoltre non utilizza la semantica di blocco cooperativo e non può essere utilizzato con cicli paralleli che hanno una dipendenza in avanti.concurrency::auto_partitioner
Divide il lavoro in un numero iniziale di intervalli (in genere il numero di thread di lavoro disponibili per lavorare con il ciclo). Il runtime utilizza questo tipo per impostazione predefinita quando non si chiama un algoritmo parallelo di overload che accetta un parametro _Partitioner. Ogni intervallo può essere suddiviso in sotto intervalli consentendo il bilanciamento del carico. Quando un intervallo di lavoro finisce, il runtime ridistribuisce sotto intervalli di lavoro degli altri thread a tale thread. Utilizzare questo partitioner se il carico di lavoro non rientra in una delle altre categorie o è necessario un supporto completo per l'annullamento o il blocco cooperativo.concurrency::simple_partitioner
Divide il lavoro in intervalli in modo che ogni intervallo dispone di almeno il numero di iterazioni che sono specificate dalla dimensione specificata del blocco. Questo tipo di partitioner partecipa al bilanciamento del carico; tuttavia, il runtime non dividere gli intervalli in sotto intervalli. Per ogni thread di lavoro, il runtime controlla l'annullamento ed esegue il bilanciamento del carico dopo che le iterazioni _Chunk_size finiscono.concurrency::static_partitioner
Divide il lavoro in un numero fisso di intervalli (in genere il numero di thread di lavoro disponibili per lavorare con il ciclo). Questo tipo di partitioner può migliorare le prestazioni poiché non utilizza l'acquisizione del lavoro e pertanto ha meno sovraccarico. Utilizzare questo tipo di partitioner quando ogni iterazione di un ciclo parallelo esegue una quantità di lavoro fissa e uniforme e non è richiesto supporto per l'annullamento o l'inoltro di blocco cooperativo.
Avviso
Gli algoritmi parallel_transform e di parallel_for_each supportano solo i contenitori che utilizzano iteratori ad accesso casuale (come std::vector) per il partizionatore statico, semplice e di affinità.L'utilizzo di contenitori che utilizzano iteratori bidirezionali e in avanti genera un errore in fase di compilazione.Il partizionatore 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 mantengono lo stato e non vengono modificati dal runtime. Di conseguenza è possibile creare questi oggetti partitioner al 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 non-const, referenza |-valore in modo che l'algoritmo possa archiviare lo stato per riutilizzarlo nei cicli futuri. L'esempio seguente mostra un'applicazione di base che esegue la stessa operazione su un set di dati in parallelo, più volte. L'utilizzo di affinity_partitioner può migliorare le prestazioni poiché l'array probabilmente è adatto 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);
}
}
Avviso
Prestare attenzione quando si modifica il codice esistente che utilizza la semantica di blocco cooperativo per utilizzare static_partitioner o affinity_partitioner.Questi tipi di partitioner non utilizzano il bilanciamento del carico o l'acquisizione dell'intervallo e quindi possono modificare il comportamento dell'applicazione.
Il modo migliore per stabilire se è opportuno utilizzare un partizionatore in un 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 potrebbe ad esempio garantire un aumento di velocità significativo in un computer con processore multi-core che presenta un numero limitato di core, ma potrebbe comportare rallentamenti in computer che presentano un numero di core relativamente elevato.
[Top]
Ordinamento parallelo
La libreria PPL fornisce tre algoritmi di ordinamento: concurrency::parallel_sort, concurrency::parallel_buffered_sort e concurrency::parallel_radixsort. Questi algoritmi di ordinamento sono utili quando si dispone di un set di dati che può trarre vantaggio dall'ordinamento in parallelo. In particolare, ordinare in parallelo è utile quando è presente un set di dati di grandi dimensioni o quando si utilizza un'operazione di confronto costosa per ordinare i dati. Ognuno di questi algoritmi ordina gli elementi sul posto.
Gli algoritmi parallel_buffered_sort e parallel_sort sono entrambi algoritmi basati sul confronto. Ovvero confrontano gli elementi per 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ò risultare più efficace di parallel_sort, ma richiede spazio O(N).
L'algoritmo parallel_radixsort è basato sull'hash. Ovvero utilizza chiavi Integer per ordinare gli elementi. Utilizzando i tasti, questo algoritmo può calcolare direttamente la destinazione di un elemento anziché utilizzare i confronti. Come parallel_buffered_sort, questo algoritmo richiede spazio O(N).
La tabella seguente riepiloga le proprietà importanti dei tre algoritmi di ordinamento parallelo.
Algoritmo |
Descrizione |
Meccanismo di ordinamento |
Stabilità di ordinamento |
Requisiti di memoria |
Complessità di tempo |
Accesso di iteratori |
|---|---|---|---|---|---|---|
parallel_sort |
Ordinamento basato sul confronto di utilizzo generale. |
Basato sul confronto (ascendente) |
Instabile |
None |
O((N/P)log(N/P) + 2N((P-1)/P)) |
Casuale |
parallel_buffered_sort |
Ordinamento basato sul confronto di utilizzo generale più veloce che richiede spazio O(N). |
Basato sul confronto (ascendente) |
Instabile |
Richiede un aggiunta di O(N) spazio |
O((N/P)log(N)) |
Casuale |
parallel_radixsort |
Ordinamento basato su chiave Integer che richiede spazio O(N). |
Basato su hash |
Stabile |
Richiede un aggiunta di O(N) spazio |
O(N/P) |
Casuale |
La figura seguente mostra graficamente le proprietà importanti dei tre algoritmi di ordinamento paralleli.
.png "Confronto degli algoritmi di ordinamento")
Questi algoritmi di ordinamento parallelo seguono le regole di gestione dell'annullamento e delle eccezioni. Per ulteriori informazioni sulla gestione dell'annullamento e delle eccezioni nel runtime di concorrenza, vedere Annullamento degli algoritmi paralleli e Gestione delle eccezioni nel runtime di concorrenza.
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 sull'operatore di assegnazione di spostamento, vedere Dichiaratore di riferimento rvalue: && e Procedura: scrivere un costruttore di spostamento.Se non viene fornito un operatore di assegnazione di spostamento o una funzione di scambio, gli algoritmi di ordinamento utilizzano il costruttore di copia.
L'esempio di base seguente illustra come utilizzare parallel_sort per ordinare 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
*/
Questo esempio mostra come fornire una funzione di confronto personalizzata. Utilizza il metodo std::complex::real per ordinare valori std::complex<double> 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)
*/
Questo esempio mostra come fornire una funzione hash all'algoritmo parallel_radixsort. Questo esempio ordina punti 3-D. 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, questo esempio utilizza un set di dati relativamente piccolo. È possibile aumentare la dimensione iniziale del vettore per sperimentare miglioramenti delle prestazioni su set di dati di grandi dimensioni.
Questo esempio utilizza un'espressione lambda come funzione hash. È inoltre possibile utilizzare una delle implementazioni predefinite della classe std::hash o definirne una propria. È inoltre possibile utilizzare un oggetto personalizzato di funzione hash, 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 essere convertibile nel tipo size_t.
Scelta di un algoritmo di ordinamento
In molti casi, parallel_sort fornisce il migliore bilanciamento delle prestazioni di memoria e di velocità. Tuttavia, come si aumenta la dimensione del set di dati, il numero di processori disponibili o della 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 dataset. In questo documento, un piccolo dataset contiene un massimo di 1.000 elementi, un dataset medio contiene tra 10.000 e 100.000 elementi e un grande dataset contiene più di 100.000 elementi.
La quantità di lavoro che la funzione di confronto o la funzione di hash esegue.
La quantità di risorse di elaborazione disponibili.
Le caratteristiche del dataset. Ad esempio, un algoritmo può risultare migliore per i dati già quasi ordinati ma non per i dati che sono completamente disordinati.
La dimensione del blocco. L'argomento facoltativo _Chunk_size specifica quando l'algoritmo passa da un'implementazione di ordinamento parallela ad una seriale di come viene suddiviso l'ordinamento globale in unità di lavoro più piccole. Ad esempio, se viene fornito 512, l'algoritmo passa ad un'implementazione seriale quando un'unità di lavoro contiene 512 elementi o meno. Un'implementazione seriale può migliorare le prestazioni complessive perché elimina il sovraccarico richiesto per elaborare i dati in parallelo.
Potrebbe non essere possibile effettuare l'ordinamento di un piccolo dataset in parallelo, anche quando si dispone di molte risorse di elaborazione o quando la funzione di confronto o la funzione hash esegue relativamente grandi quantità di lavoro. È possibile utilizzare la funzione std::sort per ordinare piccoli dataset. (parallel_sort e parallel_buffered_sort chiamano sort quando si specifica una dimensione del blocco maggiore del dataset; tuttavia, parallel_buffered_sort deve allocare spazio O(N), che potrebbe richiedere del tempo aggiuntivo a causa dei conflitti di blocco o dell'allocazione di memoria.)
Se è necessario ridurre l'utilizzo di memoria o l'allocatore di memoria è soggetto ai conflitti di blocco, utilizzare parallel_sort per ordinare un dataset di medie dimensioni. parallel_sort non richiede spazio aggiuntivo; gli altri algoritmi richiedono spazio O(N).
Utilizzare parallel_buffered_sort per ordinare dataset di medie dimensioni e quando l'applicazione soddisfa lo spazio aggiuntivo richiesto O(N). parallel_buffered_sort può essere particolarmente utile quando si dispone di molte risorse di elaborazione, di una funzione di confronto costosa o di una funzione di hash.
Utilizzare parallel_radixsort per ordinare dataset di grandi dimensioni e quando l'applicazione soddisfa la richiesta di spazio aggiuntivo O(N). parallel_radixsort può essere particolarmente utile quando l'operazione di confronto equivalente è più complessa o quando entrambe le operazioni sono dispendiose.
Avviso
Implementare una buona funzione hash richiede la conoscenza dell'intervallo di dataset e come ogni elemento nel dataset viene trasformato nel valore senza segno corrispondente.Poiché l'operazione di hash lavora su valori senza segno, si consideri una strategia di ordinamento diversa se i valori hash senza segno non possono essere prodotti.
L'esempio seguente confronta le prestazioni di sort, di parallel_sort, di parallel_buffered_sort e di parallel_radixsort su set di uguale dimensione di dati random.
// 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, presupponendo che sia possibile allocare spazio O(N) durante l'ordinamento, parallel_radixsort risulta più efficiente in questo dataset in questa configurazione del computer.
[Top]
Argomenti correlati
Titolo |
Descrizione |
|---|---|
Viene illustrato come utilizzare l'algoritmo parallel_for per eseguire la moltiplicazione di matrici. |
|
Viene illustrato come utilizzare l'algoritmo parallel_for_each per calcolare il conteggio dei numeri primi in un oggetto std::array in parallelo. |
|
Procedura: utilizzare parallel_invoke per scrivere una routine di ordinamento in parallelo |
Viene illustrato come utilizzare l'algoritmo parallel_invoke per migliorare le prestazioni dell'algoritmo di ordinamento bitonico. |
Procedura: utilizzare parallel_invoke per eseguire operazioni in parallelo |
Viene illustrato come utilizzare 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 |
Mostra come utilizzare gli algoritmi parallel_reduce e parallel_transform per eseguire un'operazione di mappa e di riduzione che conta le occorrenze di parole nei file. |
Viene descritta la libreria PPL che fornisce un modello di programmazione imperativa in grado di offrire scalabilità e semplicità per lo sviluppo di applicazioni simultanee. |
|
Viene illustrato il ruolo dell'annullamento nella libreria PPL, come annullare un lavoro parallelo e come determinare quando un gruppo di attività è annullato. |
|
Viene illustrato il ruolo di gestione delle eccezioni nel runtime di concorrenza. |