Paralelní algoritmy

Paralelní knihovnu vzorků (PPL) obsahuje algoritmy, které souběžně provádět práce na kolekcí dat.Tyto algoritmy se podobají jsou stanoveny podle šablony knihovny STL (Standard).

Paralelní algoritmy jsou složeny z existující funkce v modulu Runtime souběžnosti.Například concurrency::parallel_for algoritmus používá concurrency::structured_task_group objektu k provádění paralelní smyčky iterací.parallel_for Oddíly algoritmus pracovat s optimálně dána k dispozici počet výpočetních prostředků.

Oddíly

• Algoritmus parallel_for

• Algoritmus parallel_for_each

• Algoritmus parallel_invoke

• Algoritmy parallel_transform a parallel_reduce

  • Algoritmus parallel_transform

  • Algoritmus parallel_reduce

  • Příklad: Paralelní provádění mapování a redukce

• Rozdělení práce

• Paralelní řazení

  • Volba řadicího algoritmu

Algoritmus parallel_for

Concurrency::parallel_for algoritmu paralelně opakovaně provádí stejnou úlohu.Každý z těchto úkolů parametrizovanou hodnotu iterace.Tento algoritmus je užitečné, pokud máte vedení subjektu, který není sdílení zdrojů mezi iteracemi této smyčky.

parallel_for Algoritmus rozdělí úkoly optimálně pro paralelní spouštění.Používá práce krást algoritmus a rozsah krást na tyto oddíly v rovnováze při zatížení nevyrovnané.Když jedna iterace smyčky blokuje kooperativně, modul runtime redistribuuje rozsah iterací, přiřazené k aktuálnímu vláknu jiných podprocesů nebo zpracovatelům.Podobně velké množství iterací dokončení podprocesu modulu runtime redistribuuje práci z jiných vláken na tomto vlákně.parallel_for Algoritmus podporuje také paralelismu vnořené.Když jeden paralelní smyčka obsahuje další paralelní smyčky, modul runtime koordinuje zpracování zdrojů mezi subjekty smyčky nejúčinnějším způsobem pro paralelní spouštění.

parallel_for Algoritmus používá několik verzí přetížené.První verze má počáteční hodnotu, koncovou hodnotu a pracovní funkce (lambda výrazy, funkce objektu nebo ukazatele na funkci).Druhá verze má počáteční hodnotu, koncovou hodnotu, hodnotu kterou krok a pracovní funkce.První verze této funkce používá jako hodnota kroku 1.Zbývající verze trvat rozdělovač objekty, které umožňují určit způsob parallel_for by oddílů oblastí mezi vlákny.Rozdělovače jsou vysvětleny podrobněji v sekci Rozdělení práce v tomto dokumentu.

Je možné převést mnoho for použití smyčky parallel_for.Nicméně parallel_for algoritmus se liší od for výkazu následujícím způsobem:

• parallel_for Algoritmus parallel_for úloh nespustí v předem určeném pořadí.

• parallel_for Algoritmus nepodporuje svévolné ukončení podmínek.parallel_for Algoritmus zastavíte aktuální hodnotu proměnné iterace je menší než _Last.

• _Index_type Typ parametru musí být integrálního typu.Tento integrálního typu můžete podepsat nebo nepodepsané.

• Opakování smyčky musí být dopředu.parallel_for Algoritmus vyvolána výjimka typu std::invalid_argument -li _Step parametr je menší než 1.

• Mechanismus zpracování výjimek parallel_for algoritmu se liší od for smyčky.V případě více výjimek současně v těle paralelní smyčky, modul runtime šíří pouze jedné výjimky podprocesu, který se nazývá parallel_for.Navíc při jednom opakování smyčky vyvolá výjimku, modul runtime nezastaví bezprostředně celkové smyčky.Místo toho smyčky je umístěn ve zrušené státní a modul runtime zahodí dosud nezahájené úkoly.Další informace o zpracování výjimek a paralelních algoritmů naleznete v Zpracování výjimek v Concurrency Runtime.

I když parallel_for algoritmus nepodporuje podmínky svévolné ukončení, zrušení můžete zastavit všechny úlohy.Další informace o rušení viz Zrušení v knihovně PPL.

[!POZNÁMKA]

Plánování nákladů, že výsledky z zátěže a podporu pro funkce, jako je zrušení nemusí překonat výhody souběžně vykonávaných těla smyčky, zvláště když těla smyčky je relativně malý.Toto zatížení lze minimalizovat pomocí paralelní smyčka rozdělovač.Další informace naleznete v tématu Rozdělení práce dále v tomto dokumentu.

Příklad

Následující příklad zobrazuje základní strukturu parallel_for algoritmu.Tento příklad vytiskne každou hodnotu v rozsahu [1, 5] paralelně ke konzole.

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

Tento příklad vytvoří následující výstup:

Protože parallel_for algoritmus funguje u každé položky současně, bude měnit pořadí, ve kterém jsou vytištěny hodnoty do konzoly.

Kompletní příklad, který používá parallel_for algoritmus, viz Postupy: Programování smyčky parallel_for.

[Nahoře]

Algoritmus parallel_for_each

Concurrency::parallel_for_each algoritmus iterativní kontejneru, jaké poskytují STL současně provádí úlohy.Používá stejná Logika rozdělování, parallel_for používá algoritmus.

parallel_for_each Algoritmus podobné STL std::for_each algoritmus, s výjimkou případů, které parallel_for_each algoritmu provede úkoly současně.Podobně jako jiné paralelní algoritmy, parallel_for_each úloh nespustí v určitém pořadí.

I když parallel_for_each algoritmus funguje u iterátorů dopředu a náhodný přístup iterátory, provádí lépe s náhodným přístupem u iterátorů.

Příklad

Následující příklad zobrazuje základní strukturu parallel_for_each algoritmu.Tento příklad vytiskne konzolu pro každou hodnotu std::array objekt současně.

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

Tento příklad vytvoří následující výstup:

Protože parallel_for_each algoritmus funguje u každé položky současně, bude měnit pořadí, ve kterém jsou vytištěny hodnoty do konzoly.

Kompletní příklad, který používá parallel_for_each algoritmus, viz Postupy: Programování smyčky parallel_for_each.

[Nahoře]

Algoritmus parallel_invoke

Concurrency::parallel_invoke algoritmu provede sérii úkolů současně.Nevrací se až do dokončení jednotlivých úkolů.Tento algoritmus je užitečné, pokud máte několik nezávislých úloh, které chcete spustit současně.

parallel_invoke Algoritmus jako její parametry obsahuje řadu funkcí práce (lambda funkce, funkce objektů nebo ukazatele na funkci).parallel_invoke Algoritmus je přetížena se mezi deset a dva parametry.Každá funkce, která je předat parallel_invoke musí být nulové parametry.

Podobně jako jiné paralelní algoritmy, parallel_invoke úloh nespustí v určitém pořadí.Téma Funkční paralelismus (Concurrency Runtime) vysvětluje, jak se parallel_invoke algoritmu se týká úkolů a skupin úkolů.

Příklad

Následující příklad zobrazuje základní strukturu parallel_invoke algoritmu.V tomto příkladu volá souběžně twice funkce na tři místní proměnné a vytiskne výsledek do konzoly.

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

Tento příklad vytvoří následující výstup:

Kompletní příklady, které používají parallel_invoke algoritmus, viz Postupy: Použití algoritmu parallel_invoke k zápisu rutiny paralelního třídění a Postupy: Použití algoritmu parallel_invoke k provádění paralelních operací.

[Nahoře]

Algoritmy parallel_transform a parallel_reduce

Concurrency::parallel_transform a concurrency::parallel_reduce algoritmy jsou paralelní verze algoritmů STL std::transform a std::accumulate, respektive.Verze Runtime souběžnosti chovat jako verze STL, s tím rozdílem, že pořadí operace není určen, neboť jsou prováděny paralelně.Tyto algoritmy používáte při práci s sada, která je dostatečně velká, aby se získat výhody výkonu a škálovatelnosti z zpracovávány současně.

Důležité
parallel_transform a parallel_reduce algoritmy podporují pouze náhodný přístup, obousměrné a dále u iterátorů, protože tyto iterátorů vytvořit stabilní paměťové adresy.Navíc musí předložit tyto iterátorů non -const l hodnoty.

Algoritmus parallel_transform

Lze použít parallel transform k provedení mnoha operací paralelního zpracování dat algoritmus.Můžete například:

• Upravte jas obrazu a provádět další operace zpracování obrazu.

• Součet nebo vzít tečka produktu mezi dvěma vektory a provádět jiné číselné výpočty vektorů.

• Provádění 3D raytracing, kde každé iteraci odkazuje na jeden pixel, který je vykreslen.

Následující příklad zobrazuje základní strukturu, která je použita k volání parallel_transform algoritmu.V tomto příkladu Neguje každý prvek std::vector objektu dvěma způsoby.První způsob využívá lambda výraz.Druhý způsob využívá std::negate, která je odvozena z 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>());
}

Upozornění
Tento příklad ukazuje použití základní parallel_transform.Protože funkce práce neprovádí značné množství práce, není v tomto příkladu očekává výrazné zvýšení výkonu.

parallel_transform Algoritmus má dva přetížení.První přetížení má jeden vstupní a unární funkce.Unární funkce může být lambda výraz, který přijímá jeden argument, funkce objektu nebo typ, který je odvozen od unary_function.Druhý přetížení má dva vstupní oblasti a binární funkce.Binární funkce může být lambda výraz, který přijímá dva argumenty, funkce objektu nebo typ, který je odvozen od std::binary_function.Následující příklad ukazuje tyto rozdíly.

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

Důležité
Iterace, který zadáte pro výstup parallel_transform musí zcela překrývá vstupní iterační nebo vůbec nebudou překrývat.Tento algoritmus chování není-li iterátory vstupní a výstupní se částečně překrývají.

Algoritmus parallel_reduce

parallel_reduce Algoritmus je užitečné, pokud máte řadu operací, které vyhovují asociativní vlastnost. (Tento algoritmus nevyžaduje vlastnost komutativní.) Zde jsou některé operace, které lze provést pomocí parallel_reduce:

• Násobení řad vyrábět matice matice.

• Vynásobte posloupnost matic k výrobě vektor vektor.

• Vypočítat délku posloupnosti řetězců.

• Seznam prvků, jako jsou například řetězce, sloučit do jednoho prvku.

Základní příklad ukazuje, jak použít parallel_reduce algoritmus kombinovat posloupnosti řetězců do jednoho řetězce.Jako příklady pro parallel_transform, v tomto příkladu základní se neočekávají nárůst výkonu.

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

V mnoha případech si lze představit parallel_reduce jako zkratku pro použití parallel_for_each společně s algoritmus concurrency::combinable třídy.

Příklad: Paralelní provádění mapování a redukce

A mapy operace se týká funkce každé hodnoty v sekvenci.A snížení operace kombinuje prvky posloupnosti do jedné hodnoty.Můžete použít šablonu knihovny STL (Standard) std::transformstd::accumulate třídy provádět mapování a zmenšit operace.Mnohé problémy však lze použít parallel_transform algoritmus k provedení operace mapování paralelně a parallel_reduce algoritmus provedení operace zmenšení paralelně.

Následující příklad porovnává čas potřebný k výpočtu součtu prvočísla sériově a paralelně.Mapa fáze transformace než prvotřídní hodnoty na 0 a fáze snížit částky hodnoty.

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

Dalším příkladem, který provede mapování a zmenšit operace paralelně, viz Postupy: Paralelní provádění operací mapování a redukce.

[Nahoře]

Rozdělení práce

Učinit paralelní operace na zdroj dat, je základní krok k oddílu zdroje do více oddílů, které je přístupný souběžně více vlákny.Rozdělovač Určuje, jak by paralelního algoritmu oddílů oblastí mezi vlákny.Jak bylo uvedeno dříve v tomto dokumentu, PPL používá výchozí mechanismus, který vytvoří počáteční zatížení a potom pomocí práce krást algoritmus a krást na tyto oddíly v rovnováze při zatížení nevyrovnané rozsah rozdělení.Například oblast iterací dokončení jednoho opakování smyčky modul runtime redistribuuje práci z jiných vláken na tomto vlákně.Však pro některé scénáře, můžete chtít zadat jiné rozdělení mechanismus, který se lépe hodí pro váš problém.

parallel_for, parallel_for_each, A parallel_transform algoritmy poskytují přetížených verzí, které přebírají další parametr, _Partitioner.Tento parametr definuje rozdělovač typ, který rozděluje práci.Zde jsou druhy rozdělovače, které definuje PPL:

• Concurrency::affinity_partitioner
  Práce se rozdělí do pevný počet rozsahů (obvykle počet pracovních podprocesů, které jsou k dispozici pro práci na smyčky).Tento typ rozdělovač se podobá static_partitioner, ale mezipaměti spřažení zlepšuje způsob, jakým je mapován oblasti pracovních podprocesů.Tento typ rozdělovač může zvýšit výkon při smyčka je proveden prostřednictvím sady dat několikrát (například smyčky uvnitř smyčky) a přizpůsobí data v mezipaměti.Tento rozdělovač zrušení plně neúčastní.Je také nepoužívá spolupráce blokování sémantiku a proto jej nelze použít s paralelní smyčky, které mají závislost vpřed.

• Concurrency::auto_partitioner
  Práce se rozdělí do počáteční počet rozsahů (obvykle počet pracovních podprocesů, které jsou k dispozici pro práci na smyčky).Modul runtime používá ve výchozím nastavení tohoto typu při volání nejsou přetížené paralelního algoritmu, který má _Partitioner parametr.Každý rozsah může být rozdělen do dílčích oblastí a tím umožňuje vyrovnání zátěže dochází.Po dokončení rozsah práce, modul runtime redistribuuje dílčí oblasti práce z jiných vláken na tomto vlákně.Tento rozdělovač použijte, pokud vaše pracovní vytížení nespadá do jiných kategorií nebo vyžadují plnou podporu pro výmaz nebo blokování spolupráce.

• Concurrency::simple_partitioner
  Rozdělí se práce do oblastí tak, že každá oblast má alespoň počet iterací, které jsou určeny podle velikosti daného bloku.Tento typ rozdělovač účastní zátěže; modul runtime však nedělí rozsahů do dílčích oblastí.Pro každého zaměstnance, modul runtime hledá zrušení a provádí vyrovnávání zatížení po _Chunk_size Dokončeno iterací.

• Concurrency::static_partitioner
  Práce se rozdělí do pevný počet rozsahů (obvykle počet pracovních podprocesů, které jsou k dispozici pro práci na smyčky).Tento typ rozdělovač může zlepšit výkon, protože nepoužívá krást práci a proto má menší režii.Používáte rozdělovač, při každé iteraci paralelní smyčka provádí jednotné a pevné množství práce a vyžadují podporu pro zrušení nebo z nich dál spolupráce blokování.

Upozornění
parallel_for_each a parallel_transform algoritmy podporují pouze kontejnery, které u iterátorů náhodný přístup (jako například std::vector) pro statické, jednoduchá a spřažení rozdělovače.Používání nádob, používající obousměrné a u iterátorů dopředu vytvoří chybu v době kompilace.Výchozí rozdělovač, auto_partitioner, podporuje všechny tři typy iterátor.

Tyto rozdělovače se obvykle používají stejným způsobem, s výjimkou affinity_partitioner.Většina typů rozdělovač není udržení stavu a nejsou změněny modulem runtime.Proto můžete vytvořit tyto objekty rozdělovač v místě volání, jak je znázorněno v následujícím příkladu.

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

Však musí projít affinity_partitioner objekt, jako non -const, l hodnota odkazovat tak, že algoritmus lze uložit pro budoucí vedení znovu stát.Následující příklad ukazuje základní aplikace, který provádí stejnou operaci pro sadu dat paralelně vícekrát.Použití affinity_partitioner může zlepšit výkon, protože pole je pravděpodobné, aby se vešel do mezipaměti.

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

Upozornění
Buďte opatrní při úpravě existující kód, který je založen na společné blokování sémantiku pro použití static_partitioner nebo affinity_partitioner.Tyto typy rozdělovač nepoužívejte zátěže nebo rozsah krást a proto mohou změnit chování aplikace.

Nejlepší způsob, jak určit, zda použít v jakékoli dané situaci rozdělovač je experimentovat a změřit, jak dlouho trvá operace provést ve skupinovém rámečku Konfigurace počítače a reprezentativních zatížení.Například statické rozdělení může poskytnout významné Vančurovou vícejádrové počítače, který má pouze několik jádra, ale může dojít v počítačích s relativně mnoho jader zpomalování.

[Nahoře]

Paralelní řazení

PPL obsahuje tři algoritmy řazení: concurrency::parallel_sort, concurrency::parallel_buffered_sort, a concurrency::parallel_radixsort.Tyto algoritmy řazení jsou užitečné, pokud máte sadu dat, která mohou mít prospěch z jsou řazeny paralelně.Zejména řazení paralelně je užitečné Pokud máte velké datové sady nebo při řazení dat pomocí porovnání výpočetně náročné operace.Každý z těchto algoritmů Seřadí prvky na místě.

parallel_sort a parallel_buffered_sort jsou algoritmy, algoritmy založené na porovnání.To znamená jejich porovnání prvků podle hodnoty.parallel_sort Algoritmus je bez dalších požadavků na paměť a je vhodná pro univerzální řazení.parallel_buffered_sort Algoritmus lze provádět lepší než parallel_sort, ale vyžaduje to O(N) místa.

parallel_radixsort Algoritmus je algoritmus HMAC.To znamená používá číslo klíče řazení prvků.Pomocí kláves se tento algoritmus výpočtu přímo určení prvku namísto použití porovnávání.Jako parallel_buffered_sort, vyžaduje tento algoritmus O(N) místa.

Následující tabulka shrnuje důležité vlastnosti ze tří paralelních algoritmů řazení.

Algoritmus	Description	Mechanismus řazení	Stabilita řazení	Požadavky na paměť	Časové složitosti	Přístup iterátor
parallel_sort	Univerzální řazení založené na porovnání.	Na základě porovnání (vzestupně)	Nestabilní	Žádná	O((N/P)log(N/P) + 2N((P-1)/P))	Náhodné
parallel_buffered_sort	Rychlejší univerzální na základě porovnání řazení vyžaduje místo O(N).	Na základě porovnání (vzestupně)	Nestabilní	Vyžaduje další O(N) místa	O((N/P)log(N))	Náhodné
parallel_radixsort	Celé číslo na základě klíče řazení vyžaduje místo O(N).	Algoritmus HMAC	Stabilní	Vyžaduje další O(N) místa	O(N/P)	Náhodné

Následující obrázek znázorňuje tři paralelní algoritmy třídění důležité vlastnosti více graficky.

Tyto paralelní řazení algoritmy se řídí pravidly zrušení a zpracování výjimek.Další informace o zrušení a zpracování výjimek v modulu Runtime souběžnosti naleznete v tématu Zrušení paralelní algoritmy a Zpracování výjimek v Concurrency Runtime.

Tip

Tyto paralelní řazení algoritmy podporují přesunutí sémantiky.Můžete definovat operátor přiřazení přesun povolit odkládací operací efektivněji.Další informace o přesunutí sémantiky a operátor přiřazení přesunout, viz Deklarátor odkazu hodnoty R: &&, a Postupy: Zápis konstruktoru přesunu.Pokud nezadáte operátor přiřazení přesunout nebo zaměnit funkci řazení algoritmy použít kopie konstruktoru.

Základní příklad ukazuje, jak použít parallel_sort k řazení vector z int hodnoty.Ve výchozím nastavení parallel_sort používá std::less k porovnání hodnot.

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

Tento příklad ukazuje, jak poskytnout vlastní porovnání funkce.Používá std::complex::real metoda řazení std::complex<dvojité> hodnot ve vzestupném pořadí.

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

Tento příklad ukazuje, jak poskytnout funkce hash parallel_radixsort algoritmu.V tomto příkladu jsou 3D bodů.Body jsou seřazeny podle jejich vzdálenosti od referenčního bodu.

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

Pro ilustraci v tomto příkladu relativně malou sadu dat.Můžete zvýšit počáteční velikost vektoru vyzkoušet i přes větší sady dat výkonu.

Tento příklad používá lambda výraz jako funkce hash.Můžete také některé předdefinované implementace rozhraní std::hash třídy nebo definovat vlastní specializace.Také můžete vlastní hash funkce objektu, jak je uvedeno v následujícím příkladu:

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

Funkce hash musí vrátit integrálního typu (std::is_integral::value musí být true).Tento typ integrální musí být převést na zadejte size_t.

Volba řadicího algoritmu

V mnoha případech parallel_sort poskytuje nejlepší kompromis výkon rychlost a paměť.Však zvětšit velikost množiny dat, počet procesorů, které jsou k dispozici nebo složitosti porovnání funkce, jako je parallel_buffered_sort nebo parallel_radixsort může fungovat lépe.Nejlepší způsob, jak zjistit, který algoritmus řazení pro použití v jakémkoli daném scénáři je experimentovat a změřit, jak dlouho trvá řadit Typická data za reprezentativní konfiguraci počítače.Pokud zvolíte řazení strategie, vzít v úvahu následující pokyny.

• Velikost datové sady.V tomto dokumentu malé dataset obsahuje prvky, méně než 1 000, Střední dataset obsahuje mezi 10 000 a 100 000 prvky a velký dataset obsahuje prvky více než 100 000.

• Množství práce, která provádí porovnání funkce nebo funkce hash.

• Částka k dispozici výpočetních prostředků.

• Vlastnosti datové sady.Jeden algoritmus může například provádět i pro data, která je již téměř seřazeny, ale není také pro data, která je zcela neseřazenými.

• Velikost bloku.Nepovinný _Chunk_size argument určuje, kdy algoritmus přepne z paralelní provádění sériové řazení jak ji rozděluje celkové řazení na menší jednotky práce.Například pokud zadáte 512, algoritmus přepne do sériového provedení pracovní jednotka obsahuje prvky 512 nebo méně.Sériové provedení může zlepšit celkový výkon, protože eliminuje režii, který je vyžadován ke zpracování dat současně.

Nemusí být výhodné řadit malou sadu dat paralelně, i když máte velký počet dostupných výpočetních prostředků nebo porovnání funkce nebo funkce hash provádí poměrně velké množství práce.Můžete použít std::sort funkce řazení malých objektů DataSet. (parallel_sort a parallel_buffered_sort volat sort -li zadat velikost bloku, který je větší než dataset; Nicméně, parallel_buffered_sort musel přidělit O(N) místa, která by mohla trvat déle kvůli konfliktu nebo paměti přidělení zámku.)

Pokud je třeba z důvodu úspory paměti nebo je modul pro přidělování paměti zámků, použijte parallel_sort řazení střední třída dataset.parallel_sortvyžaduje větší mezery; jiné algoritmy vyžadují O(N) místa.

Použití parallel_buffered_sort řadit středně velkých datových sad a pokud splňuje další aplikace O(N) místa požadavku.parallel_buffered_sortmůže být zvláště užitečné, když máte velký počet výpočetních prostředků nebo nákladné porovnání funkce nebo funkce hash.

Použití parallel_radixsort k řazení velkých sad dat a pokud splňuje další aplikace O(N) požadavku místo.parallel_radixsortmůže být užitečná, jestliže je dražší operace porovnání rovnocenné nebo kdy jsou nákladné operace.

Upozornění
Implementace Kvalitní zatřiďovací funkce je třeba znát rozsah datové sady a jak každý element v objektu dataset je transformován do odpovídající hodnota bez znaménka.Vzhledem k tomu, že transformace pracuje na nepodepsané hodnoty, zvažte různé řazení strategie Pokud nepodepsané hodnoty hash hodnoty nemohou být předloženy.

Následující příklad porovnává výkon sort, parallel_sort, parallel_buffered_sort, a parallel_radixsort proti velké stejnou sadu náhodná 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.
*/

V tomto příkladu, který předpokládá, že je přijatelné pro přidělení O(N) místa během řazení, parallel_radixsort na tento objekt dataset v této konfiguraci počítače provede nejlepší.

[Nahoře]

Příbuzná témata

Title	Description
Postupy: Programování smyčky parallel_for	Ukazuje, jak použít parallel_for algoritmus provádět násobení matice.
Postupy: Programování smyčky parallel_for_each	Ukazuje, jak použít parallel_for_each algoritmus k výpočtu počtu prvočísel v std::array objekt současně.
Postupy: Použití algoritmu parallel_invoke k zápisu rutiny paralelního třídění	Ukazuje, jak použít algoritmus parallel_invoke pro zlepšení výkonu bitonického algoritmu řazení.
Postupy: Použití algoritmu parallel_invoke k provádění paralelních operací	Ukazuje, jak použít algoritmus parallel_invoke pro zlepšení výkonu programu, který provádí více operací ve sdíleném zdroji dat.
Postupy: Paralelní provádění operací mapování a redukce	Ukazuje, jak použít parallel_transform a parallel_reduce algoritmy provádět mapování a zmenšit operace, která spočítá výskyty slova v souborech.
Knihovna PPL (Parallel Patterns Library)	Popisuje PPL, který poskytuje imperativní programovací model, který podporuje škálovatelnost a snadné použití pro vývoj aplikací současně.
Zrušení v knihovně PPL	Vysvětluje roli zrušení PPL, jak zrušit paralelní práce a jak lze zjistit, kdy je zrušena skupina úloh.
Zpracování výjimek v Concurrency Runtime	Vysvětluje roli zpracování výjimek v modulu Runtime souběžnosti.

Odkaz

parallel_for – funkce

parallel_for_each – funkce

parallel_invoke – funkce

affinity_partitioner – třída

auto_partitioner – třída

simple_partitioner – třída

static_partitioner – třída

parallel_sort – funkce

parallel_buffered_sort – funkce

parallel_radixsort – funkce