Paralelní algoritmy

Knihovna PPL (Parallel Patterns Library) poskytuje algoritmy, které souběžně provádějí práci na kolekcích dat. Tyto algoritmy se podobají těm, které poskytuje standardní knihovna jazyka C++.

Paralelní algoritmy se skládají z existujících funkcí v concurrency Runtime. Například souběžnost::p arallel_for algoritmu používá objekt concurrency::structured_task_group k provádění paralelních iterací smyčky. Algoritmy parallel_for fungují optimálním způsobem vzhledem k dostupnému počtu 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

• Práce dělení

• Paralelní řazení

  • Volba algoritmu řazení

Algoritmus parallel_for

Souběžnost ::p arallel_for algoritmu opakovaně provádí stejnou úlohu paralelně. Každá z těchto úloh je parametrizována hodnotou iterace. Tento algoritmus je užitečný, pokud máte tělo smyčky, které nesdílí prostředky mezi iteracemi této smyčky.

Algoritmus parallel_for rozděluje úlohy optimálním způsobem pro paralelní spouštění. Používá algoritmus krádeže práce a rozsah krádeží k vyrovnávání těchto oddílů, když jsou úlohy nevyvážené. Když jedna smyčka iterace blokuje spolupráci, modul runtime redistribuuje rozsah iterací, které jsou přiřazeny k aktuálnímu vláknu do jiných vláken nebo procesorů. Podobně, když vlákno dokončí rozsah iterací, modul runtime redistribuuje práci z jiných vláken do tohoto vlákna. Algoritmus parallel_for také podporuje vnořený paralelismus. Pokud jedna paralelní smyčka obsahuje jinou paralelní smyčku, modul runtime koordinuje zpracování prostředků mezi těly smyčky efektivním způsobem pro paralelní spuštění.

Algoritmus parallel_for má několik přetížených verzí. První verze přebírá počáteční hodnotu, koncovou hodnotu a pracovní funkci (výraz lambda, objekt funkce nebo ukazatel funkce). Druhá verze přebírá počáteční hodnotu, koncovou hodnotu, hodnotu, o kterou se má krokovat, a pracovní funkci. První verze této funkce používá jako hodnotu kroku hodnotu 1. Zbývající verze přebírají objekty partitioneru, které umožňují určit, jak parallel_for mají být rozsahy oddílů mezi vlákny. Oddíly jsou podrobněji vysvětleny v oddílu Práce dělení v tomto dokumentu.

Můžete převést mnoho for smyček na použití parallel_for. Algoritmus parallel_for se ale liší od for příkazu následujícími způsoby:

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

• Algoritmus parallel_for nepodporuje libovolné podmínky ukončení. Algoritmus parallel_for se zastaví, když aktuální hodnota proměnné iterace je jedna menší než last.

• Parametr _Index_type typu musí být celočíselným typem. Tento celočíselný typ může být podepsán nebo bez znaménka.

• Iterace smyčky musí být vpřed. Algoritmus parallel_for vyvolá výjimku typu std::invalid_argument , pokud _Step je parametr menší než 1.

• Mechanismus zpracování výjimek pro parallel_for algoritmus se liší od for mechanismu smyčky. Pokud v těle paralelní smyčky dojde současně k více výjimkám, modul runtime rozšíří pouze jednu z výjimek do vlákna, které volal parallel_for. Kromě toho, když jedna iterace smyčky vyvolá výjimku, modul runtime okamžitě nezastaví celkovou smyčku. Místo toho se smyčka umístí do zrušeného stavu a modul runtime zahodí všechny úlohy, které ještě nebyly spuštěny. Další informace o zpracování výjimek a paralelních algoritmech najdete v tématu Zpracování výjimek.

parallel_for I když algoritmus nepodporuje libovolné podmínky ukončení, můžete zrušení použít k zastavení všech úloh. Další informace o zrušení naleznete v tématu Zrušení v PPL.

Poznámka:

Náklady na plánování, které vyplývají z vyrovnávání zatížení a podpory funkcí, jako je zrušení, nemusí překonat výhody paralelního provádění těla smyčky, zejména pokud je tělo smyčky relativně malé. Tuto režii můžete minimalizovat pomocí rozdělovače v paralelní smyčce. Další informace naleznete v části Práce dělení dále v tomto dokumentu.

Příklad

Následující příklad ukazuje základní strukturu parallel_for algoritmu. Tento příklad se vypíše do konzoly každou hodnotu v rozsahu [1, 5] paralelně.

// 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í ukázkový výstup:

1 2 4 3 5

parallel_for Vzhledem k tomu, že algoritmus funguje na každé položce paralelně, bude se lišit pořadí, ve kterém se hodnoty vytisknou do konzoly.

Úplný příklad, který používá algoritmus, najdete v parallel_for tématu Postupy: Zápis smyčky parallel_for.

[Nahoře]

Algoritmus parallel_for_each

Souběžnost ::p arallel_for_each algoritmu provádí úlohy v iterativním kontejneru, jako jsou například úlohy poskytované standardní knihovnou jazyka C++, paralelně. Používá stejnou logiku parallel_for dělení, jakou algoritmus používá.

Algoritmus parallel_for_each připomíná algoritmus std::for_each knihovny C++ s tím rozdílem, že parallel_for_each algoritmus provádí úlohy souběžně. Stejně jako jiné paralelní algoritmy parallel_for_each nespustí úlohy v určitém pořadí.

parallel_for_each I když algoritmus funguje na iterátorech předávání i iterátorech náhodného přístupu, funguje lépe s iterátory náhodného přístupu.

Příklad

Následující příklad ukazuje základní strukturu parallel_for_each algoritmu. Tento příklad vytiskne do konzoly každou hodnotu v objektu std::array paralelně.

// 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í ukázkový výstup:

4 5 1 2 3

parallel_for_each Vzhledem k tomu, že algoritmus funguje na každé položce paralelně, bude se lišit pořadí, ve kterém se hodnoty vytisknou do konzoly.

Úplný příklad, který používá algoritmus, najdete v parallel_for_each tématu Postupy: Zápis smyčky parallel_for_each.

[Nahoře]

Algoritmus parallel_invoke

Algoritmus concurrency::p arallel_invoke spouští sadu úloh paralelně. Nevrací se, dokud se každý úkol nedokončí. Tento algoritmus je užitečný, pokud máte několik nezávislých úloh, které chcete spustit současně.

Algoritmus parallel_invoke přebírá jako parametry řadu pracovních funkcí (funkce lambda, objekty funkcí nebo ukazatele na funkce). Algoritmus parallel_invoke je přetížen tak, aby převzal mezi dvěma a deseti parametry. Každá funkce, kterou předáte, musí obsahovat parallel_invoke nulové parametry.

Stejně jako jiné paralelní algoritmy parallel_invoke nespustí úlohy v určitém pořadí. Téma Paralelismus úkolů vysvětluje, jak parallel_invoke algoritmus souvisí s úkoly a skupinami úkolů.

Příklad

Následující příklad ukazuje základní strukturu parallel_invoke algoritmu. Tento příklad souběžně volá twice funkci na třech místních proměnných 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:

108 11.2 HelloHello

Kompletní příklady, které používají algoritmus, najdete v parallel_invoke tématu Postupy: Použití parallel_invoke k zápisu rutiny paralelního řazení a postupy: Použití parallel_invoke ke spouštění paralelních operací.

[Nahoře]

Algoritmy parallel_transform a parallel_reduce

Souběžnost::p arallel_transform a concurrency::p arallel_reduce algoritmy jsou paralelními verzemi algoritmů standardní knihovny C++ std::transform a std::kumulují. Verze modulu Concurrency Runtime se chovají jako verze standardní knihovny C++ s tím rozdílem, že pořadí operací není určeno, protože se spouští paralelně. Tyto algoritmy použijte, když pracujete se sadou, která je dostatečně velká, abyste získali výhody paralelního zpracování výkonu a škálovatelnosti.

Důležité

parallel_reduce Algoritmy parallel_transform podporují pouze náhodný přístup, obousměrné a předávací iterátory, protože tyto iterátory vytvářejí stabilní adresy paměti. Tyto iterátory musí také produkovat jiné nežconst l-hodnoty.

Algoritmus parallel_transform

Algoritmus parallel transform můžete použít k provádění mnoha operací paralelizace dat. Je například možné:

• Upravte jas obrázku a proveďte další operace zpracování obrazu.

• Součet nebo převezměte tečkovaný součin mezi dvěma vektory a proveďte další číselné výpočty s vektory.

• Proveďte 3D trasování paprsků, kde každá iterace odkazuje na jeden pixel, který se musí vykreslit.

Následující příklad ukazuje základní strukturu, která se používá k volání parallel_transform algoritmu. Tento příklad neguje každý prvek objektu std::vector dvěma způsoby. První způsob používá výraz lambda. Druhý způsob používá std::negate, který je odvozen od 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>());
}

Upozorňující

Tento příklad ukazuje základní použití parallel_transform. Vzhledem k tomu, že pracovní funkce neprovádí značné množství práce, v tomto příkladu se neočekává významné zvýšení výkonu.

Algoritmus parallel_transform má dvě přetížení. První přetížení přebírá jeden vstupní rozsah a unární funkci. Unární funkce může být výraz lambda, který přebírá jeden argument, objekt funkce nebo typ odvozený z unary_function. Druhé přetížení přebírá dva vstupní rozsahy a binární funkci. Binární funkce může být výraz lambda, který přebírá dva argumenty, objekt funkce nebo typ odvozený z std::binary_function. Následující příklad znázorňuje 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é

Iterátor, který zadáte pro výstup, parallel_transform se musí úplně překrývat vstupní iterátor nebo se vůbec nepřekrývá. Chování tohoto algoritmu není určeno, pokud se vstupní a výstupní iterátory částečně překrývají.

Algoritmus parallel_reduce

Algoritmus parallel_reduce je užitečný, pokud máte posloupnost operací, které vyhovují asociativní vlastnosti. (Tento algoritmus nevyžaduje commutativní vlastnost.) Tady jsou některé operace, se kterými můžete provádět parallel_reduce:

• Násobení sekvencí matic pro vytvoření matice

• Vynásobte vektor posloupností matic k vytvoření vektoru.

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

• Zkombinujte seznam prvků, jako jsou řetězce, do jednoho prvku.

Následující základní příklad ukazuje, jak pomocí parallel_reduce algoritmu zkombinovat posloupnost řetězců do jednoho řetězce. Stejně jako u příkladů se parallel_transformv tomto základním příkladu neočekává zvýšení 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{
      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.
*/

V mnoha případech si můžete představit parallel_reduce zkratku pro použití parallel_for_each algoritmu společně s souběžností::combinable třídy.

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

Operace mapování použije funkci na každou hodnotu v posloupnosti. Operace redukce kombinuje prvky sekvence do jedné hodnoty. K provádění operací mapování a redukce můžete použít funkce std::transform a std::kumulovat funkce C++. V případě mnoha problémů však můžete algoritmus použít parallel_transform k paralelní operaci mapování a parallel_reduce algoritmus provádí operaci redukce paralelně.

Následující příklad porovnává dobu potřebnou k výpočtu součtu primárních čísel sériově a paralelně. Fáze mapování transformuje nenáčinné hodnoty na 0 a fáze redukce sečte 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ší příklad, který paralelně provádí operaci mapování a redukce, najdete v tématu Postupy: Provádění operací mapování a redukce paralelně.

[Nahoře]

Práce dělení

Pokud chcete paralelně paralelizovat operaci ve zdroji dat, je základním krokem rozdělení zdroje do několika oddílů, ke kterým může přistupovat souběžně více vláken. Rozdělovač určuje, jak má paralelní algoritmus rozdělit rozsahy mezi vlákny. Jak jsme si vysvětlili dříve v tomto dokumentu, PPL používá výchozí mechanismus dělení, který vytvoří počáteční úlohu a pak používá algoritmus krádeže práce a rozsah krádeže k vyvážení těchto oddílů, když jsou úlohy nevyvážené. Například když jedna iterace smyčky dokončí rozsah iterací, modul runtime redistribuuje práci z jiných vláken do tohoto vlákna. V některých scénářích ale můžete chtít zadat jiný mechanismus dělení, který je pro váš problém vhodnější.

, parallel_forparallel_for_eacha parallel_transform algoritmy poskytují přetížené verze, které přebírají další parametr, _Partitioner. Tento parametr definuje typ rozdělovače, který rozděluje práci. Tady jsou typy rozdělovačů, které PPL definuje:

souběžnost::affinity_partitioner
Rozdělí práci na pevný počet oblastí (obvykle počet pracovních vláken, které jsou k dispozici pro práci ve smyčce). Tento typ partitioneru static_partitionerse podobá , ale zlepšuje spřažení mezipaměti tím, že mapuje rozsahy na pracovní vlákna. Tento typ partitioneru může zvýšit výkon při provádění smyčky ve stejné sadě dat vícekrát (například smyčka v rámci smyčky) a data se vejdou do mezipaměti. Tento partitioner se plně nezaúčastní zrušení. Nepoužívá také sémantiku blokování spolupráce, a proto ji nelze použít s paralelními smyčkami, které mají závislost vpřed.

souběžnost::auto_partitioner
Rozdělí práci na počáteční počet oblastí (obvykle počet pracovních vláken, které jsou k dispozici pro práci ve smyčce). Modul runtime ve výchozím nastavení používá tento typ, pokud nevoláte přetížený paralelní algoritmus, který přebírá _Partitioner parametr. Každá oblast je možné rozdělit do dílčích oblastí a tím umožnit vyrovnávání zatížení. Po dokončení rozsahu práce modul runtime redistribuuje dílčí rozsahy práce z jiných vláken do tohoto vlákna. Tento dělicí nástroj použijte, pokud vaše úloha nepatří do jedné z dalších kategorií nebo vyžadujete plnou podporu pro blokování zrušení nebo spolupráce.

souběžnost::simple_partitioner
Rozdělí práci na rozsahy tak, aby každá oblast má alespoň počet iterací určených danou velikostí bloku dat. Tento typ rozdělovače se účastní vyrovnávání zatížení; Modul runtime však nerozděluje rozsahy do dílčích rozsahů. U každého pracovního procesu modul runtime kontroluje zrušení a provádí vyrovnávání zatížení po _Chunk_size dokončení iterací.

souběžnost::static_partitioner
Rozdělí práci na pevný počet oblastí (obvykle počet pracovních vláken, které jsou k dispozici pro práci ve smyčce). Tento typ partitioneru může zvýšit výkon, protože nepoužívá krádeže práce, a proto má menší režii. Tento typ rozdělovače použijte, když každá iterace paralelní smyčky provádí pevnou a jednotnou velikost práce a nevyžadujete podporu pro zrušení nebo přesměrování blokování spolupráce.

Upozorňující

parallel_transform Algoritmy parallel_for_each podporují pouze kontejnery, které pro statické, jednoduché a spřažení používají iterátory náhodného přístupu (například std::vector). Použití kontejnerů, které používají obousměrné a předávací iterátory, způsobí chybu v době kompilace. Výchozí dělicí modul auto_partitionerpodporuje všechny tři z těchto typů iterátoru.

Tyto oddíly se obvykle používají stejným způsobem, s výjimkou affinity_partitioner. Většina typů partitioneru neudržuje stav a modul runtime je nemění. Proto můžete tyto objekty partitioneru vytvořit v lokalitě 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());
}

Je však nutné předat affinity_partitioner objekt jako odkaz na nehodnocenouconst hodnotu, aby algoritmus mohl uložit stav pro budoucí smyčky pro opakované použití. Následující příklad ukazuje základní aplikaci, která provádí stejnou operaci s datovou sadou paralelně vícekrát. Použití affinity_partitioner může zvýšit výkon, protože pole se pravděpodobně vejde 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í

Při úpravě existujícího kódu, který spoléhá na spolupráci blokující sémantiku k použití static_partitioner nebo affinity_partitioner. Tyto typy rozdělovačů nepoužívají vyrovnávání zatížení nebo krádež rozsahu, a proto mohou změnit chování vaší aplikace.

Nejlepším způsobem, jak určit, jestli se má v libovolném scénáři použít partitioner, je experimentovat a měřit, jak dlouho trvá dokončení operací v rámci reprezentativních zatížení a konfigurací počítače. Statické dělení může například výrazně zrychlit na počítači s více jádry, který má pouze několik jader, ale může způsobit zpomalení na počítačích s relativně velkým počtem jader.

[Nahoře]

Paralelní řazení

PPL poskytuje tři algoritmy řazení: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort a concurrency::p arallel_radixsort. Tyto algoritmy řazení jsou užitečné, pokud máte datovou sadu, která může těžit z paralelního řazení. Řazení paralelně je užitečné zejména v případě, že máte velkou datovou sadu nebo když k řazení dat používáte výpočetně náročnou operaci porovnání. Každý z těchto algoritmů seřadí prvky na místě.

parallel_buffered_sort Oba parallel_sort algoritmy jsou založené na porovnání. To znamená, že porovnávají prvky podle hodnoty. Algoritmus parallel_sort nemá žádné další požadavky na paměť a je vhodný pro řazení pro obecné účely. Algoritmus parallel_buffered_sort může fungovat lépe než parallel_sort, ale vyžaduje prostor O(N).

Algoritmus parallel_radixsort je založený na hodnotě hash. To znamená, že k řazení prvků používá celočíselné klíče. Pomocí klíčů může tento algoritmus místo porovnání přímo vypočítat cíl prvku. Podobně jako parallel_buffered_sorttento algoritmus vyžaduje mezeru typu O(N).

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

Algoritmus	Popis	Mechanismus řazení	Stabilita řazení	Požadavky na paměť	Časová složitost	Přístup iterátoru
parallel_sort	Řazení založené na porovnání pro obecné účely	Porovnání na základě (vzestupně)	Nestabilní	Nic	O((N/P)log(N/P) + 2N((P-1)/P))	Náhodné
parallel_buffered_sort	Rychlejší řazení založené na porovnání pro obecné účely, které vyžaduje mezeru typu O(N).	Porovnání na základě (vzestupně)	Nestabilní	Vyžaduje další prostor O(N).	O((N/P)log(N))	Náhodné
parallel_radixsort	Celočíselné řazení založené na klíčích, které vyžaduje mezeru typu O(N).	Založené na hodnotě hash	Stable	Vyžaduje další prostor O(N).	O(NENÍ_K_DISPOZICI)	Náhodné

Následující obrázek znázorňuje důležité vlastnosti tří algoritmů paralelního řazení graficky.

Tyto paralelní algoritmy řazení se řídí pravidly zpracování zrušení a výjimek. Další informace o zpracování zrušení a výjimek v modulu Concurrency Runtime naleznete v tématu Zrušení paralelních algoritmů a zpracování výjimek.

Tip

Tyto paralelní algoritmy řazení podporují sémantiku přesunutí. Můžete definovat operátor přiřazení přesunutí, který umožní efektivnější provádění operací prohození. Další informace o sémantice přesunu a operátoru přiřazení přesunutí naleznete v tématu Deklarátor odkazů Rvalue: &&a Konstruktory přesunutí a Operátory přiřazení přesunutí (C++). Pokud nezadáte operátor přiřazení přesunutí nebo funkci prohození, algoritmy řazení používají konstruktor kopírování.

Následující základní příklad ukazuje, jak se používá parallel_sort k řazení vectorint hodnot. Ve výchozím nastavení parallel_sort se k porovnání hodnot používá std::less .

// 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ávanou funkci. Používá metodu std::complex::real k řazení hodnot std::complex<double> 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 algoritmus funkci parallel_radixsort hash. Tento příklad seřadí 3D body. Body jsou seřazené 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 tento příklad používá relativně malou datovou sadu. Můžete zvětšit počáteční velikost vektoru pro experimentování s vylepšením výkonu u větších sad dat.

Tento příklad používá výraz lambda jako funkci hash. Můžete také použít jednu z předdefinovaných implementací třídy std::hash nebo definovat vlastní specializaci. Můžete také použít objekt vlastní funkce hash, jak je znázorněno v tomto 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 celočíselný typ (std::is_integral::value musí být true). Tento celočíselný typ musí být konvertibilní na typ size_t.

Volba algoritmu řazení

V mnoha případech parallel_sort poskytuje nejlepší rovnováhu mezi rychlostí a výkonem paměti. Když ale zvětšíte velikost sady dat, počet dostupných procesorů nebo složitost porovnávané funkce nebo parallel_buffered_sortparallel_radixsort může fungovat lépe. Nejlepším způsobem, jak určit, který algoritmus řazení se má použít v libovolném scénáři, je experimentovat a měřit, jak dlouho trvá řazení typických dat v reprezentativních konfiguracích počítače. Při výběru strategie řazení mějte na paměti následující pokyny.

• Velikost datové sady V tomto dokumentu obsahuje malá datová sada méně než 1 000 prvků, střední datová sada obsahuje 10 000 až 100 000 prvků a velká datová sada obsahuje více než 100 000 prvků.

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

• Množství dostupných výpočetních prostředků.

• Vlastnosti vaší datové sady Například jeden algoritmus může dobře fungovat pro data, která jsou již téměř seřazená, ale ne pro data, která jsou zcela neseřazená.

• Velikost bloku dat. Volitelný _Chunk_size argument určuje, kdy algoritmus přepne paralelně na implementaci sériového řazení, protože rozdělí celkové řazení do menších jednotek práce. Pokud například zadáte hodnotu 512, algoritmus se přepne na sériovou implementaci, pokud jednotka práce obsahuje 512 nebo méně prvků. Sériová implementace může zlepšit celkový výkon, protože eliminuje režijní náklady potřebné ke paralelnímu zpracování dat.

Nemusí být vhodné seřadit malou datovou sadu paralelně, i když máte velký počet dostupných výpočetních prostředků nebo porovnávací funkci nebo funkci hash provádí poměrně velkou práci. K řazení malých datových sad můžete použít funkci std::sort . (parallel_sort a parallel_buffered_sort volání sort při zadání velikosti bloku, která je větší než datová sada; parallel_buffered_sort museli byste ale přidělit prostor O(N), což by mohlo trvat delší dobu kvůli kolizí uzamčení nebo přidělení paměti.)

Pokud potřebujete šetřit paměť nebo alokátor paměti podléhá kolizím zámků, použijte parallel_sort k seřazení střední datové sady. parallel_sort nevyžaduje žádné další místo; ostatní algoritmy vyžadují mezeru O(N).

Slouží parallel_buffered_sort k seřazení středně velkých datových sad a k tomu, když vaše aplikace splňuje dodatečný požadavek na prostor O(N). parallel_buffered_sort může být užitečné zejména v případech, kdy máte velký počet výpočetních prostředků nebo nákladnou porovnávací funkci nebo funkci hash.

Slouží parallel_radixsort k seřazení velkých datových sad a k tomu, když vaše aplikace splňuje další požadavek na prostor O(N). parallel_radixsort může být užitečné zejména v případech, kdy je ekvivalentní operace porovnání dražší nebo když jsou obě operace nákladné.

Upozornění

Implementace dobré hashové funkce vyžaduje, abyste znali rozsah datových sad a způsob transformace jednotlivých prvků v datové sadě na odpovídající nepodepsanou hodnotu. Vzhledem k tomu, že operace hash funguje u nepodepsaných hodnot, zvažte jinou strategii řazení, pokud nelze vytvořit nepodepsané hodnoty hash.

Následující příklad porovnává výkon sort, , parallel_sortparallel_buffered_sorta parallel_radixsort proti stejné velké množině náhodných dat.

// 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 se předpokládá, že přiřazování prostoru O(N) během řazení parallel_radixsort je nejvhodnější pro tuto datovou sadu v této konfiguraci počítače.

[Nahoře]

Příbuzná témata

Titulek	Popis
Postupy: Programování smyčky parallel_for	Ukazuje, jak pomocí parallel_for algoritmu 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 primárních čísel v objektu std::array paralelně.
Postupy: Použití algoritmu parallel_invoke k zápisu rutiny paralelního třídění	Ukazuje, jak použít parallel_invoke algoritmus ke zlepšení výkonu algoritmu řazení bitových hodnot.
Postupy: Použití algoritmu parallel_invoke k provádění paralelních operací	Ukazuje, jak použít parallel_invoke algoritmus ke zlepšení výkonu programu, který provádí více operací se sdíleným zdrojem dat.
Postupy: Paralelní provádění operací mapování a redukce	Ukazuje, jak pomocí parallel_transformparallel_reduce algoritmů provést operaci mapování a redukce, která počítá výskyty slov 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 souběžných aplikací.
Zrušení v knihovně PPL	Vysvětluje roli zrušení v PPL, jak zrušit paralelní práci a jak určit, kdy je skupina úloh zrušena.
Zpracování výjimek	Vysvětluje roli zpracování výjimek v concurrency Runtime.

Reference

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