Parallella algoritmer

PPL (Parallel Patterns Library) innehåller algoritmer som samtidigt utför arbete med datasamlingar. Dessa algoritmer liknar de som tillhandahålls av C++ Standard Library.

De parallella algoritmerna består av befintliga funktioner i Concurrency Runtime. Till exempel använder algoritmen concurrency::parallel_for ett objekt av typen concurrency::structured_task_group för att utföra de parallella upprepningarna i loopen. parallel_for Algoritmpartitionerna fungerar på ett optimalt sätt med tanke på det tillgängliga antalet beräkningsresurser.

Sektioner

• Parallel_for-algoritmen

• Algoritmen parallel_for_each

• Parallel_invoke-algoritmen

• Algoritmerna parallel_transform och parallel_reduce

  • Parallel_transform-algoritmen

  • Parallel_reduce-algoritmen

  • Exempel: Utföra karta och minska parallellt

• Partitioneringsarbete

• Parallell sortering

  • Välja en sorteringsalgoritm

Algoritmen parallel_for

Concurrency::parallel_for-algoritmen utför upprepade gånger samma uppgifter parallellt. Var och en av dessa uppgifter parametriseras av ett iterationsvärde. Den här algoritmen är användbar när du har en loopens kropp där varje iteration inte delar resurser.

Algoritmen parallel_for delar upp uppgifter på ett optimalt sätt för parallell körning. Den använder en algoritm för arbetsstöld och räckviddsstöld för att balansera de här partitionerna när arbetsbelastningarna är obalanserade. När en loop-iteration blockeras på ett samarbetsinriktat sätt fördelar körmiljön om den räckvidd av iterationer som är tilldelad den aktuella tråden till andra trådar eller processorer. På samma sätt, när en tråd slutför ett antal iterationer, omfördelar körningen arbete från andra trådar till aktuell tråd. Algoritmen parallel_for stöder också kapslad parallellitet. När en parallell loop innehåller en annan parallell loop samordnar exekveringen bearbetningsresurser mellan looparnas kroppar på ett effektivt sätt för parallell exekvering.

Algoritmen parallel_for har flera överlagrade versioner. Den första versionen tar ett startvärde, ett slutvärde och en arbetsfunktion (ett lambda-uttryck, funktionsobjekt eller funktionspekare). Den andra versionen tar ett startvärde, ett slutvärde, ett värde som du ska stega efter och en arbetsfunktion. Den första versionen av den här funktionen använder 1 som stegvärde. De återstående versionerna tar partitioneringsobjekt, vilket gör att du kan ange hur parallel_for partitionsintervall ska fördelas mellan trådar. Partitioner förklaras mer detaljerat i avsnittet Arbete med partitionering i det här dokumentet.

Du kan konvertera många for loopar till att använda parallel_for. Algoritmen parallel_for skiljer sig dock från -instruktionen for på följande sätt:

• Algoritmen parallel_forparallel_for kör inte uppgifterna i en fördefinierad ordning.

• Algoritmen parallel_for stöder inte godtyckliga avslutningsvillkor. Algoritmen parallel_for stoppas när det aktuella värdet för iterationsvariabeln är en mindre än last.

• Typparametern _Index_type måste vara en integrerad typ. Den här integraltypen kan signeras eller osigneras.

• Loop-iterationen måste vara framåt. Algoritmen parallel_for genererar ett undantag av typen std::invalid_argument om parametern _Step är mindre än 1.

• Mekanismen för undantagshantering för algoritmen parallel_for skiljer sig från en for loop. Om flera undantag inträffar samtidigt i en parallell loopkropp, sprider körsystemet bara ett av undantagen till tråden som anropade parallel_for. När en loop-iteration dessutom utlöser ett undantag stoppar körningen inte omedelbart den övergripande loopen. I stället placeras loopen i avbrutet tillstånd och körningen tar bort alla aktiviteter som ännu inte har startats. Mer information om undantagshantering och parallella algoritmer finns i Undantagshantering.

Även om algoritmen parallel_for inte stöder godtyckliga avslutningsvillkor kan du använda annullering för att stoppa alla uppgifter. Mer information om annullering finns i Annullering i PPL.

Exempel

I följande exempel visas algoritmens parallel_for grundläggande struktur. I det här exemplet skrivs varje värde ut till konsolen i intervallet [1, 5] parallellt.

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

I det här exemplet skapas följande exempelutdata:

1 2 4 3 5

Eftersom algoritmen parallel_for fungerar parallellt med varje objekt varierar ordningen i vilken värdena skrivs ut till konsolen.

Ett fullständigt exempel som använder algoritmen finns i parallel_forHow to: Write a parallel_for Loop (Så här skriver du en parallel_for Loop).

[Topp]

Algoritmen för parallel_for_each

Algoritmen concurrency::parallel_for_each utför parallellt uppgifter på en iterativ behållare, till exempel de som tillhandahålls av C++ Standard Library. Den använder samma partitioneringslogik som algoritmen parallel_for använder.

Algoritmen parallel_for_each liknar C++ Standard Library std::for_each-algoritmen , förutom att algoritmen parallel_for_each kör uppgifterna samtidigt. Precis som andra parallella algoritmer parallel_for_each kör inte uppgifterna i en viss ordning.

Även om algoritmen parallel_for_each fungerar på både vidarebefordrande iteratorer och iteratorer för slumpmässig åtkomst presterar den bättre med iteratorer för slumpmässig åtkomst.

Exempel

I följande exempel visas algoritmens parallel_for_each grundläggande struktur. I det här exemplet skrivs varje värde ut till konsolen i ett std::array-objekt parallellt.

// 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
*/

I det här exemplet skapas följande exempelutdata:

4 5 1 2 3

Eftersom algoritmen parallel_for_each fungerar parallellt med varje objekt varierar ordningen i vilken värdena skrivs ut till konsolen.

Ett fullständigt exempel som använder algoritmen finns i parallel_for_eachSå här skriver du en parallel_for_each-loop.

[Topp]

Algoritmen parallel_invoke

Algoritmen concurrency::p arallel_invoke kör en uppsättning uppgifter parallellt. Den returneras inte förrän varje aktivitet har slutförts. Den här algoritmen är användbar när du har flera oberoende uppgifter som du vill köra samtidigt.

Algoritmen parallel_invoke tar som parametrar en serie arbetsfunktioner (lambda-funktioner, funktionsobjekt eller funktionspekare). Algoritmen parallel_invoke är överbelastad för att ta mellan två och tio parametrar. Varje funktion som du skickar till parallel_invoke måste ha noll parametrar.

Precis som andra parallella algoritmer parallel_invoke kör inte uppgifterna i en viss ordning. I avsnittet Aktivitetsparallellitet förklaras hur algoritmen parallel_invoke relaterar till uppgifter och aktivitetsgrupper.

Exempel

I följande exempel visas algoritmens parallel_invoke grundläggande struktur. I det här exemplet anropas twice funktionen samtidigt på tre lokala variabler och resultatet skrivs ut till konsolen.

// 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;
}

Det här exemplet genererar följande utdata:

108 11.2 HelloHello

Fullständiga exempel som använder algoritmen parallel_invoke finns i How to: Use parallel_invoke to Write a Parallel Sort Routine and How to: Use parallel_invoke to Execute Parallel Operations (Använda parallel_invoke för att skriva en parallell sorteringsrutin ) och Så här använder du parallel_invoke för att köra parallella åtgärder.

[Topp]

Algoritmerna parallel_transform och parallel_reduce

concurrency::parallel_transform och concurrency::parallel_reduce-algoritmerna är parallella versioner av C++ Standard Library-algoritmerna std::transform respektive std::accumulate. Concurrency Runtime-versionerna fungerar som C++-standardbiblioteksversionerna, förutom att åtgärdsordningen inte bestäms eftersom de körs parallellt. Använd dessa algoritmer när du arbetar med en uppsättning som är tillräckligt stor för att få prestanda- och skalbarhetsfördelar genom att bearbetas parallellt.

Algoritmen parallel_transform

Du kan använda algoritmen parallel transform för att utföra många dataparallelliseringsåtgärder. Till exempel kan du:

• Justera ljusstyrkan för en bild och utför andra bildbearbetningsåtgärder.

• Summera eller ta punktprodukten mellan två vektorer och utför andra numeriska beräkningar på vektorer.

• Utför 3D-ray-spårning, där varje iteration refererar till en pixel som måste återges.

I följande exempel visas den grundläggande struktur som används för att anropa algoritmen parallel_transform . I det här exemplet negeras varje element i ett std::vector-objekt på två sätt. Det första sättet använder ett lambda-uttryck. Det andra sättet använder std::negate, som härleds från 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>());
}

Algoritmen parallel_transform har två överlagringar. Den första överlagringen tar ett indataintervall och en unär funktion. Unary-funktionen kan vara ett lambda-uttryck som tar ett argument, ett funktionsobjekt eller en typ som härleds från unary_function. Den andra överlagringen tar två indataintervall och en binär funktion. Den binära funktionen kan vara ett lambda-uttryck som tar två argument, ett funktionsobjekt eller en typ som härleds från std::binary_function. I följande exempel visas dessa skillnader.

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

Algoritmen "parallel_reduce"

Algoritmen parallel_reduce är användbar när du har en sekvens med åtgärder som uppfyller den associativa egenskapen. (Den här algoritmen kräver inte den kommutativa egenskapen.) Här är några av de åtgärder som du kan utföra med parallel_reduce:

• Multiplicera matrissekvenser för att skapa en matris.

• Multiplicera en vektor med en sekvens med matriser för att skapa en vektor.

• Beräkna längden på en sekvens med strängar.

• Kombinera en lista med element, till exempel strängar, till ett element.

Följande grundläggande exempel visar hur du använder algoritmen parallel_reduce för att kombinera en sekvens med strängar till en sträng. Precis som med exemplen för parallel_transformförväntas prestandavinster inte i det här grundläggande exemplet.

// 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.
*/

I många fall kan du se parallel_reduce det som en förkortning för användningen av algoritmen parallel_for_each tillsammans med klassen concurrency::combinable .

Exempel: Utföra Map och Reduce parallellt

En kartåtgärd tillämpar en funktion på varje värde i en sekvens. En reduce-åtgärd kombinerar elementen i en sekvens till ett värde. Du kan använda C++-standardbiblioteket funktionerna std::transform och std::accumulate för att utföra map- och reduce-operationer. För många problem kan du dock använda algoritmen parallel_transform för att utföra kartåtgärden parallellt och algoritmen parallel_reduce utför reduce-åtgärden parallellt.

I följande exempel jämförs den tid det tar att beräkna summan av primtal seriellt och parallellt. Kartfasen omvandlar icke-primära värden till 0 och reduce-fasen summerar värdena.

// 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
*/

Ett annat exempel som utför en map- och reduce-åtgärd parallellt finns i How to: Perform Map and Reduce Operations in Parallel (Så här utför du map- och reduce-åtgärder parallellt).

[Topp]

Arbete med partitionering

För att parallellisera en åtgärd på en datakälla är ett viktigt steg att partitionera källan i flera avsnitt som kan nås samtidigt av flera trådar. En partitioner specificerar hur en parallell algoritm ska dela upp områden mellan trådar. Som beskrivs tidigare i det här dokumentet använder PPL en standardpartitioneringsmekanism som skapar en inledande arbetsbelastning och sedan använder en algoritm för arbetsstöld och intervallstöld för att balansera dessa partitioner när arbetsbelastningarna är obalanserade. När en loop-iteration till exempel slutför ett antal iterationer distribuerar körningen om arbete från andra trådar till den tråden. För vissa scenarier kanske du vill ange en annan partitioneringsmekanism som passar bättre för ditt problem.

parallel_forAlgoritmerna , parallel_for_eachoch parallel_transform ger överlagrade versioner som tar ytterligare en parameter, _Partitioner. Den här parametern definierar den partitionerartyp som delar upp arbetet. Här är de typer av partitioner som PPL definierar:

konkurrens::affinity_partitioner
Delar upp arbetet i ett fast antal intervall (vanligtvis antalet arbetstrådar som är tillgängliga för att arbeta med loopen). Den här partitionerartypen liknar static_partitioner, men förbättrar cachetillhörigheten genom att mappa intervall till arbetstrådar. Den här partitionerartypen kan förbättra prestanda när en loop körs över samma datauppsättning flera gånger (till exempel en loop i en loop) och data får plats i cacheminnet. Den här partitioneraren deltar inte fullt ut i annulleringen. Den använder inte heller samarbetsblockeringssemantik och kan därför inte användas med parallella loopar som har ett framåtberoende.

konkurrens::auto-partitioner
Delar upp arbetet i ett antal initiala intervall (vanligtvis antalet arbetstrådar som är tillgängliga för att arbeta med slingan). Körningsmiljön använder den här typen som standard när du inte anropar en överbelastad parallell algoritm som har en _Partitioner parameter. Varje intervall kan delas in i underområden och därmed göra det möjligt att belastningsutjämning sker. När en mängd arbete har slutförts distribuerar körningen om delområden av arbete från andra trådar till den tråden. Använd den här partitioneraren om din arbetsbelastning inte omfattas av någon av de andra kategorierna eller om du behöver fullständigt stöd för annullering eller samarbetsblockering.

parallellitet::simple_partitioner
Delar upp arbetet i intervall så att varje intervall har minst det antal iterationer som anges av den angivna segmentstorleken. Den här partitioneringstypen deltar i belastningsutjämningen. Körmiljön delar dock inte upp intervall i underintervall. För varje anställd kontrollerar körningen om annullering har skett och utför belastningsutjämning efter att _Chunk_size iterationer har slutförts.

samtidighet::static_partitioner
Delar upp arbetet i ett fast antal intervall (vanligtvis antalet arbetstrådar som är tillgängliga för att arbeta med loopen). Den här partitioneringstypen kan förbättra prestandan eftersom den inte använder arbetsstöld och därför har mindre omkostnader. Använd den här partitioneringstypen när varje iteration av en parallell loop utför en fast och konsekvent mängd arbete och du inte behöver stöd för annullering av operationen eller framåtriktad samarbetsblockering.

Dessa partitioner används vanligtvis på samma sätt, förutom .affinity_partitioner De flesta partitioneringstyper behåller inte tillståndsdata och ändras inte av körningstiden. Därför kan du skapa dessa partitioneringsobjekt på anropsplatsen, som du ser i följande exempel.

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

Du måste dock skicka ett affinity_partitioner objekt som en icke-const, l-värdesreferens så att algoritmen kan lagra tillstånd för att återanvända i framtida loopar. I följande exempel visas ett grundläggande program som utför samma åtgärd på en datauppsättning parallellt flera gånger. Användningen av affinity_partitioner kan förbättra prestandan eftersom matrisen troligen får plats i cacheminnet.

// 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);
    }
}

Det bästa sättet att avgöra om du ska använda en partitionerare i ett visst scenario är att experimentera och mäta hur lång tid det tar att slutföra åtgärder under representativa belastningar och datorkonfigurationer. Statisk partitionering kan till exempel ge betydande hastighet på en dator med flera kärnor som bara har några kärnor, men det kan leda till långsammare prestanda på datorer som har relativt många kärnor.

[Topp]

Parallell sortering

PPL innehåller tre sorteringsalgoritmer: concurrency::parallel_sort, concurrency::parallel_buffered_sort, och concurrency::parallel_radixsort. Dessa sorteringsalgoritmer är användbara när du har en datauppsättning som kan dra nytta av att sorteras parallellt. I synnerhet är sortering parallellt användbart när du har en stor datamängd eller när du använder en beräkningsmässigt dyr jämförelseåtgärd för att sortera dina data. Varje av dessa algoritmer sorterar element på plats.

parallel_sort Algoritmerna och parallel_buffered_sort är båda jämförelsebaserade algoritmer. De jämför alltså element efter värde. Algoritmen parallel_sort har inga ytterligare minneskrav och är lämplig för allmän sortering. Algoritmen parallel_buffered_sort kan prestera bättre än parallel_sort, men den kräver O(N) utrymme.

Algoritmen parallel_radixsort är hash-baserad. Det vill säga, den använder heltalsnycklar för att sortera elementen. Med hjälp av nycklar kan den här algoritmen direkt beräkna målet för ett element i stället för att använda jämförelser. Precis som parallel_buffered_sortkräver den här algoritmen O(N) utrymme.

I följande tabell sammanfattas de viktiga egenskaperna för de tre parallella sorteringsalgoritmerna.

Följande bild visar de viktiga egenskaperna för de tre parallella sorteringsalgoritmerna mer grafiskt.

Dessa parallella sorteringsalgoritmer följer reglerna för annullering och undantagshantering. Mer information om annullering och undantagshantering i Samtidighetskörning finns i Avbryta parallella algoritmer och undantagshantering.

Följande grundläggande exempel visar hur du använder parallel_sort för att sortera värden vectorint . Som standard parallel_sort använder std::less för att jämföra värden.

// 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
*/

Det här exemplet visar hur du tillhandahåller en anpassad jämförelsefunktion. Den använder metoden std::complex::real för att sortera std::complex<double> värden i stigande ordning.

// 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)
*/

Det här exemplet visar hur du tillhandahåller en hash-funktion till algoritmen parallel_radixsort . I det här exemplet sorteras 3D-punkter. Punkterna sorteras baserat på avståndet från en referenspunkt.

// 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
*/

Som illustration använder det här exemplet en relativt liten datauppsättning. Du kan öka den ursprungliga storleken på vektorn för att experimentera med prestandaförbättringar jämfört med större datauppsättningar.

I det här exemplet används ett lambda-uttryck som hash-funktionen. Du kan också använda en av de inbyggda implementeringarna av klassen std::hash eller definiera din egen specialisering. Du kan också använda ett anpassat hash-funktionsobjekt, som du ser i det här exemplet:

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

Hash-funktionen måste returnera en integraltyp (std::is_integral::value måste vara true). Den här integraltypen måste vara konvertibel till typ size_t.

Välja en sorteringsalgoritm

I många fall parallel_sort ger den bästa balansen mellan hastighet och minnesprestanda. Men när du ökar storleken på din datamängd, antalet tillgängliga processorer eller komplexiteten i jämförelsefunktionen eller parallel_buffered_sortparallel_radixsort kan prestera bättre. Det bästa sättet att avgöra vilken sorteringsalgoritm som ska användas i ett visst scenario är att experimentera och mäta hur lång tid det tar att sortera typiska data under representativa datorkonfigurationer. Tänk på följande riktlinjer när du väljer en sorteringsstrategi.

• Storleken på din datamängd. I det här dokumentet innehåller en liten datamängd färre än 1 000 element, en medelhög datamängd innehåller mellan 10 000 och 100 000 element och en stor datamängd innehåller mer än 100 000 element.

• Mängden arbete som jämförelsefunktionen eller hashfunktionen utför.

• Mängden tillgängliga databehandlingsresurser.

• Egenskaperna för din datauppsättning. En algoritm kan till exempel fungera bra för data som redan är nästan sorterade, men inte lika bra för data som är helt osorterade.

• Segmentstorleken Det valfria _Chunk_size argumentet anger när algoritmen växlar från en parallell till en seriell sorteringsimplementering eftersom den delar upp den övergripande sorteringen i mindre arbetsenheter. Om du till exempel anger 512 växlar algoritmen till serieimplementering när en arbetsenhet innehåller 512 eller färre element. En seriell implementering kan förbättra den övergripande prestandan eftersom den eliminerar de kostnader som krävs för att bearbeta data parallellt.

Det kanske inte är värt att sortera en liten datamängd parallellt, även om du har ett stort antal tillgängliga beräkningsresurser eller om din jämförelsefunktion eller hash-funktion utför en relativt stor mängd arbete. Du kan använda funktionen std::sort för att sortera små datamängder. (parallel_sort och parallel_buffered_sort anropa sort när du anger en segmentstorlek som är större än datauppsättningen; men parallel_buffered_sort måste allokera O(N) mängd utrymme, vilket kan ta ytterligare tid på grund av låskonflikt eller minnesallokering.)

Om du måste spara minne eller om minnesallokeraren är utsatt för låskonkurrens kan du använda parallel_sort för att sortera en medelstor datamängd. parallel_sort kräver inget ytterligare utrymme. de andra algoritmerna kräver O(N) utrymme.

Använd parallel_buffered_sort för att sortera medelstora datamängder och när ditt program uppfyller ytterligare O(N) utrymmeskrav. parallel_buffered_sort kan vara särskilt användbart när du har ett stort antal beräkningsresurser eller en dyr jämförelsefunktion eller hashfunktion.

Använd parallel_radixsort för att sortera stora datamängder och när ditt program uppfyller ytterligare O(N) utrymmeskrav. parallel_radixsort kan vara särskilt användbart när motsvarande jämförelseåtgärd är dyrare eller när båda åtgärderna är dyra.

I följande exempel jämförs prestanda sortför , parallel_sort, parallel_buffered_sortoch parallel_radixsort med samma stora uppsättning slumpmässiga data.

// 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.
*/

I det här exemplet, som förutsätter att det är acceptabelt att allokera O(N) utrymme under sorteringen, parallel_radixsort presterar bäst på den här datauppsättningen på den här datorkonfigurationen.

[Topp]

Relaterade ämnen

Hänvisning

parallel_for funktion

parallel_for_each funktion

parallel_invoke funktion

affinity_partitioner-klass

auto_partitioner-klass

SimplePartitioner-klass

statisk_partitionerar-klass

parallel_sort funktion

parallel_buffered_sort funktion

parallel_radixsort funktion