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.Ad esempio, l'algoritmo di concurrency::parallel_for utilizza un oggetto di 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
Algoritmo parallel_for
Algoritmo parallel_for_each
Algoritmo parallel_invoke
Gli algoritmi di parallel_reduce e di parallel_transform
L'algoritmo di parallel_transform
L'algoritmo di parallel_reduce
Esempio: Esegue il mapping e ridurre in parallelo
Suddivisione lavoro
Ordinamento parallela
- Scegliere un algoritmo di ordinamento
Algoritmo parallel_for
L'algoritmo di 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 e un intervallo di) che rubano 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 di parallel_for dispone di diverse 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 partitioner, che consentono di specificare la modalità parallel_for deve suddividere gli intervalli tra i thread.I partitioner vengono 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 il sovraccarico utilizza un partitioner nel ciclo parallelo.Per ulteriori informazioni, vedere più avanti Suddivisione lavoro in questo documento.
.gif "Dd470426.collapse_all(it-it,VS.110).gif")
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.
[Parte superiore]
Algoritmo parallel_for_each
L'algoritmo di 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), begin(values), [](int value) {
wstringstream ss;
ss << value << L' ';
wcout << ss.str();
});
}
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.
[Parte superiore]
Algoritmo parallel_invoke
L'algoritmo di 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.
[Parte superiore]
Gli algoritmi di parallel_reduce e di parallel_transform
Gli algoritmi di concurrency::parallel_reduce e di concurrency::parallel_transform sono versioni parallele degli algoritmi std::transform e std::accumulateSTL, rispettivamente.Le versioni del runtime di concorrenza si comportano come le versioni di IL fatto che l'ordine di operazione non è determinato da eseguire in parallelo.Utilizzare questi algoritmi quando si utilizzano un set che è sufficiente ottenere i vantaggi di scalabilità e di prestazioni da essere elaborato in parallelo.
.gif "Nota importante") Importante |
|---|
Gli algoritmi di parallel_reduce e di parallel_transform supportano solo casuale, bidirezionali e inoltrare gli iteratori poiché questi iteratori producono gli indirizzi di memoria stabili.Inoltre, questi iteratori devono generare i valori non l-value diconst. |
L'algoritmo di parallel_transform
È possibile utilizzare l'algoritmo di parallel transform per eseguire molte operazioni della parallelizzazione di dati.Ad esempio, è possibile:
Regolare la luminosità di un'immagine ed eseguire altre operazioni di elaborazione di immagini.
Somma assumere il prodotto scalare di due vettori ed eseguire altri calcoli numerici sui vettori.
Eseguire l'analisi tridimensionale spoke, in cui ogni iterazione fa riferimento a un pixel che deve essere eseguito il rendering.
Nell'esempio seguente viene mostrata la struttura di base utilizzata per chiamare l'algoritmo di parallel_transform.In questo esempio nega ogni elemento di un oggetto di std::vector in due modi.La prima modalità utilizza un'espressione lambda.La seconda modalità 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>());
}
| Attenzione |
|---|
In questo esempio viene illustrato l'utilizzo di base di parallel_transform.Poiché la funzione lavoro non esegue una quantità significativa di lavoro, un importante crescita le prestazioni non è previsto in questo esempio. |
L'algoritmo di 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 seguente illustra tali 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 |
|---|
Un iteratore fornite per l'output di parallel_transform completamente deve sovrapporsi all'iteratore di input o non sovrapposti affatto.Il comportamento di questo algoritmo viene omesso se gli iteratori di output e input parzialmente si sovrappongono. |
L'algoritmo di parallel_reduce
L'algoritmo di parallel_reduce è utile quando è presente una sequenza di operazioni che soddisfano la proprietà associativa.Questo algoritmo non richiede la proprietà commutativa). Di seguito sono riportate alcune delle operazioni eseguibili con parallel_reduce:
Moltiplicare le sequenze di matrici per generare 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 elemento.
Nell'esempio di base seguente esempio viene illustrato come utilizzare l'algoritmo di parallel_reduce per combinare una sequenza di stringhe in una stringa.Come con esempi per parallel_transform, i vantaggi 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, può essere considerato come parallel_reduce un metodo sintetico per l'utilizzo dell'algoritmo di parallel_for_each insieme alla classe di concurrency::combinable.
Esempio: Esegue il mapping e ridurre 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 di (STL) std::transformstd::accumulate la libreria di modelli per eseguire il mapping e ridurre le operazioni.Tuttavia, per molti problemi, è possibile utilizzare l'algoritmo di parallel_transform per eseguire l'operazione di mapping in parallelo e l'algoritmo di parallel_reduce esegue l'operazione di riduzione in parallelo.
Nell'esempio seguente viene confrontato il tempo richiesto per calcolare la somma dei numeri primi in serie e in parallelo.I valori della scelta di trasformazioni della fase di mapping su 0 e la fase di riduzione somma dei 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 in cui viene eseguito il mapping e riduce un'operazione in parallelo, vedere Procedura: eseguire operazioni di mapping e riduzione in parallelo.
[Parte superiore]
Suddivisione lavoro
Per parallelizzare un'operazione su un'origine dati, un passaggio è fondamentale di suddividere l'origine in sezioni in cui è possibile accedere contemporaneamente da più thread.Un partitioner specifica come un algoritmo parallelo deve suddividere gli intervalli tra i thread.Come illustrato in precedenza in questo documento, la libreria PPL utilizza un meccanismo partizionante predefinito che crea un carico di lavoro iniziale e utilizza un algoritmo e un intervallo di) che rubano per bilanciare le partizioni quando i carichi di lavoro non sono bilanciati.Ad esempio, quando un'iterazione del ciclo viene completato un intervallo di iterazioni, il runtime ridistribuisce il lavoro degli altri thread a tale thread.Tuttavia, per alcuni scenari, possibile specificare un meccanismo partizionante diversa più adatto al problema.
parallel_for, parallel_for_eache algoritmi di parallel_transform forniscono 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 esecuzione in un numero fisso di intervalli (in genere il numero di thread di lavoro disponibili per modificare il ciclo).Questo tipo di partitioner assomiglia a static_partitioner, ma migliora l'affinità della cache in materia che esegue il mapping degli intervalli ai thread di lavoro.Questo tipo di partitioner può migliorare le prestazioni durante un ciclo viene eseguito durante lo stesso più volte il set di dati (ad esempio un ciclo interno di un ciclo) e i dati hanno sinistra nella cache.Il partitioner completamente non fa parte dell'annullamento.Inoltre non utilizza la semantica di blocco cooperativo e non può essere utilizzato con cicli paralleli che presentano una dipendenza in avanti.concurrency::auto_partitioner
Divide esecuzione in un numero iniziale di intervalli (in genere il numero di thread di lavoro disponibili per modificare il ciclo).Il runtime utilizza questo tipo per impostazione predefinita quando non si chiama un algoritmo parallelo di overload che accetta un parametro di _Partitioner.Ogni intervallo può essere suddiviso in sub-team intervalli e pertanto consente al bilanciamento del carico per verificare.Quando una possibilità di lavoro completata, il runtime ridistribuisce secondarie gli intervalli di lavoro da 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 funzionano in intervalli in modo che ogni intervallo dispone di almeno il numero di iterazioni specificate dalla dimensione specificata di blocco.Questo tipo di partitioner partecipa al bilanciamento del carico, tuttavia, il runtime non dividere gli intervalli in un intervallo.Per ogni thread di lavoro, il runtime per l'annullamento ed esegue il bilanciamento del carico dopo che le iterazioni di _Chunk_size completamento.concurrency::static_partitioner
Divide esecuzione in un numero fisso di intervalli (in genere il numero di thread di lavoro disponibili per modificare il ciclo).Questo tipo di partitioner può migliorare le prestazioni perché non utilizza la funzionalità di work-stealing e pertanto sono meno sovraccarico.Utilizzare questo tipo di partitioner quando ogni iterazione di un ciclo parallelo esegue una quantità di lavoro fissa e uniforme e non richiede il supporto per l'annullamento o non inoltrate il blocco cooperativo.
| Attenzione |
|---|
Gli algoritmi di parallel_transform e di parallel_for_each supportano solo i contenitori che utilizzano gli iteratori di accesso casuale (come std::vector) per il tipo statico, semplice e i partitioner di affinità.L'utilizzo di contenitori che utilizzano gli iteratori bidirezionali e in avanti genera un errore in fase di compilazione.Il partitioner predefinito, auto_partitioner, supporta tutti e tre i tipi di iteratore. |
In genere, questi non 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 di partitioner il 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 comeconstnon, di affinity_partitioner l-value in modo da poter archiviare l'algoritmo lo stato dei cicli futuri riutilizzare.Nell'esempio seguente viene illustrata un'applicazione di base che esegue la stessa operazione su più volte un set di dati in parallelo.L'utilizzo di affinity_partitioner può migliorare le prestazioni poiché la matrice è probabile adattarsi alla cache.
// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
using namespace concurrency;
int wmain()
{
// Create an arry 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 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 non variano acquisizione e pertanto possono modificare il comportamento dell'applicazione. |
Il modo migliore per stabilire se utilizzare un partitioner in qualsiasi scenario specificato consiste nel testare 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.
[Parte superiore]
Ordinamento parallela
La libreria PPL fornisce tre algoritmi di ordinamento: concurrency::parallel_sort, concurrency::parallel_buffered_sorte concurrency::parallel_radixsort.Questi algoritmi di ordinamento sono utili quando è un set di dati che può trarre vantaggio dall'ordinamento in parallelo.In particolare, ordinare in parallelo è utile in presenza di un dataset o quando si utilizza un'operazione di confronto a livello di più costosa per ordinare i dati.Ognuno di questi elementi di base degli algoritmi sul posto.
Gli algoritmi di parallel_buffered_sort e di parallel_sort sono entrambi gli algoritmi basati sul confronto.Ovvero confrontano gli elementi per valore.L'algoritmo di parallel_sort non presenta requisiti di memoria aggiuntivi e è appropriato per l'ordinamento di utilizzo generale.L'algoritmo di parallel_buffered_sort può risultare più efficace di parallel_sort, ma richiede spazio di O(N).
L'algoritmo di parallel_radixsort è basato su hash.Ovvero utilizza le chiavi Integer per ordinare gli elementi.Utilizzando i tasti, questo algoritmo è direttamente calcolare la destinazione di un elemento anziché utilizzare confronti.Come parallel_buffered_sort, questo algoritmo richiede spazio di O(N).
Nella tabella seguente vengono riepilogate le proprietà importanti dei tre algoritmi paralleli di ordinamento.
L'algoritmo |
Descrizione |
Dispositivo di selezione |
Stabilità di ordinamento |
Requisiti di memoria |
Complessità di tempo |
Accesso iteratori |
|---|---|---|---|---|---|---|
parallel_sort |
All'ordinamento basato confrontare di utilizzo generale. |
Basato Confrontare (salendo) |
Instabile |
Nessuno |
O((N/P)log(N/P) + 2N((P-1)/P)) |
Casuale |
parallel_buffered_sort |
All'ordinamento basato confrontare per tutti gli utilizzi più veloce che richiede la O (N) spazio. |
Basato Confrontare (salendo) |
Instabile |
Richiede spazio aggiuntivo di O(N) |
O((N/P)log(N)) |
Casuale |
parallel_radixsort |
All'ordinamento basato su chiave intero che richiede la O (N) spazio. |
Basato su hash |
Stabile |
Richiede spazio aggiuntivo di O(N) |
O(N/P) |
Casuale |
Nella figura riportata più graficamente le proprietà importanti dei tre algoritmi paralleli di ordinamento.
.png "Confronto degli algoritmi di ordinamento")
Questi algoritmi paralleli di ordinamento seguono le regole di annullamento e di gestione delle eccezioni.Per ulteriori informazioni sull'annullamento e la gestione delle eccezioni nel runtime di concorrenza, vedere Annullamento degli algoritmi paralleli e Gestione delle eccezioni nel runtime di concorrenza.
.gif "Suggerimento") Suggerimento |
|---|
La semantica di spostamento di supporto di questi algoritmi di ordinamento.È possibile definire un operatore di assegnazione di spostamento per abilitare le operazioni di riporto per verificare più efficiente.Per ulteriori informazioni sulla semantica di spostamento e l'operatore di assegnazione di spostamento, vedere Dichiarazione di riferimento Rvalue: &&e Procedura: Scrivere un costruttore di spostamento.Se non viene fornita una funzione di operatore di assegnazione o di scambio di spostamento, gli algoritmi di ordinamento utilizzano il costruttore di copia. |
Nell'esempio di base seguente esempio viene illustrato come utilizzare parallel_sort per ordinare vector dei valori di 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 un oggetto personalizzato confrontare la funzione.Utilizza il metodo di std::complex::real per ordinare i valori di 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)
*/
In questo esempio viene illustrato come fornire una funzione hash per l'algoritmo di parallel_radixsort.In questo esempio vengono ordinati i punti 3-d.I punti vengono ordinati in base al proprio 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
*/
Per completezza, in questo esempio viene utilizzato un set di dati relativamente piccolo.È possibile aumentare la dimensione iniziale del vettore per sperimentare miglioramenti delle prestazioni su più set di dati di grandi dimensioni.
In questo esempio viene utilizzata un'espressione lambda come funzione hash.È inoltre possibile utilizzare una delle implementazioni predefinite della classe di std::hash o definire la propria competenza.È inoltre possibile utilizzare un oggetto personalizzato di funzione hash, come illustrato nel seguente 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 in digitare size_t.
Scegliere un algoritmo di ordinamento
In molti casi, parallel_sort fornisce il bilanciamento ottimale delle prestazioni di memoria e della velocità.Tuttavia, come si aumenta la dimensione del set di dati, il numero di processori disponibili, o della complessità del confronto la funzione, parallel_buffered_sort o parallel_radixsort risultano migliori.La migliore per stabilire quale algoritmo di ordinamento utilizzare in qualsiasi scenario specificato consiste nel testare e misurare il tempo ai dati tipici di ordinamento nelle configurazioni di computer che li rappresentano.Mantenere le linee guida seguenti presente 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 compresa tra 10.000 e 100.000 elementi e di un dataset contiene più di 100.000 elementi.
La quantità di lavoro richiesta dal confrontare la funzione o la funzione hash esegue.
La quantità di risorse di elaborazione disponibili.
Le caratteristiche del dataset.Ad esempio, un algoritmo può eseguire correttamente per i dati già quasi vengono ordinati, ma non anche per i dati che sono completamente non ordinati.
Le dimensioni del blocco.L'argomento facoltativo di _Chunk_size specifica quando le opzioni dell'algoritmo da un parallelo a un'implementazione seriale di ordinamento che suddivide ordinamento globale in unità più piccole di lavoro.Ad esempio, se si forniscono 512, le opzioni di algoritmo a un'implementazione seriale a un'unità di lavoro contiene 512 o meno elementi.Un'implementazione seriale può migliorare le prestazioni globali di eliminare il sovraccarico richiesto per elaborare i dati in parallelo.
Potrebbe non essere possibile effettuare l'ordinamento un piccolo dataset in parallelo, anche quando si dispone di molte risorse di elaborazione disponibili o il confronto la funzione o la funzione hash esegue relativamente grandi quantità di lavoro.È possibile utilizzare la funzione di std::sort per ordinare i 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 di O(N), in grado di richiedere tempo aggiuntivo a causa di conflitti di blocco o dell'allocazione di memoria.)
Per risparmiare memoria o un 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 lo spazio di O(N).
Utilizzare parallel_buffered_sort per ordinare i dataset di medie dimensioni e l'applicazione soddisfa il ingombro aggiuntivo di O(N).parallel_buffered_sort può essere particolarmente utile quando si dispone di molte risorse di elaborazione o un dispendioso per confrontare la funzione o la funzione hash.
Utilizzare parallel_radixsort per ordinare i grandi dimensioni e l'applicazione soddisfa il ingombro aggiuntivo di O(N).parallel_radixsort può essere particolarmente utile quando l'operazione di confronto equivalente richiede più o quando entrambe le operazioni sono dispendiose.
| Attenzione |
|---|
Implementare una buona funzione hash necessario conoscere l'intervallo di dataset ed ogni elemento nel dataset viene applicata a un valore unsigned corrispondente.Poiché funzionamento delle operazioni hash su valori senza segno, si consideri una strategia diverso di ordinamento se senza segno valori hash non possono essere prodotti. |
Nell'esempio confronta le prestazioni di sort, di parallel_sort, di parallel_buffered_sorte di parallel_radixsort lo stesso set di dati di grandi dimensioni casuali.
// 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, si presuppone che sia possibile allocare spazio di O(N) durante l'ordinamento, parallel_radixsort risulta più efficiente nel dataset in questa configurazione del computer.
[Parte superiore]
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 |
Viene illustrato come utilizzare gli algoritmi di parallel_reduce e di parallel_transform per eseguire il mapping e ridurre operazione che conta le occorrenze delle 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. |