Paralelní algoritmy

Paralelní vzory knihovny (PPL) poskytuje algoritmy, které současně provádějí práce s 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 objekt, který chcete provést iterace paralelní smyčky.parallel_for Algoritmus oddíly fungovat optimálně dána k dispozici počet výpočetních prostředků.

Oddíly

• Parallel_for algoritmus

• Parallel_for_each algoritmus

• Parallel_invoke algoritmus

• Algoritmy parallel_transform a parallel_reduce

  • Parallel_transform algoritmus

  • Parallel_reduce algoritmus

  • Příklad: Provádění mapování a snížit paralelně

• Rozdělení práce

• Paralelní řazení

  • Volba třídění algoritmus

Parallel_for algoritmus

Concurrency::parallel_for algoritmus opakovaně provádí stejnou úlohu paralelně.Každý z těchto úkolů parametrizovanou hodnotu iterace.Tento algoritmus je užitečné, pokud máte smyčky subjekt, který není sdílení zdrojů mezi iterací 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 vyvážit tyto oddíly při zatížení nevyrovnané.V případě, že jedna iterace smyčky blokuje kooperativně za, modul runtime redistribuuje oblast iterací, která je přiřazena k aktuálnímu vláknu jiných podprocesů nebo zpracovatelům.Podobně když podproces dokončí škálu iterací, modul runtime redistribuuje práci z jiných vláken na toto vlákno.parallel_for Algoritmus podporuje také vnořené paralelnost.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 má několik přetížené verze.První verze má počáteční hodnotu a koncovou hodnotu funkce práce (lambda výrazu, funkce objektu nebo ukazatel na funkci).Druhá verze má počáteční hodnota, koncovou hodnotu, hodnotu, kterým 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, jak parallel_for by oddílů oblastí mezi vlákny.Rozdělovače jsou vysvětleny podrobněji v části Rozdělení práce v tomto dokumentu.

Je možné převést mnoho for smyčky pomocí parallel_for.Nicméně parallel_for algoritmus se liší od for prohlášení následujícími způsoby:

• parallel_for Algoritmus parallel_for nespustí v předem pořadí úkolů.

• 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 typ integrální můžete podepsán 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 algoritmus odlišuje od toho for smyčky.Je-li více výjimek současných v těle paralelní smyčky, modul runtime šíří pouze některá z výjimek vlákna, která se nazývá parallel_for.Navíc pokud jedna iterace smyčky vyvolá výjimku, modul runtime není okamžité zastavení celkové smyčky.Místo toho smyčky je umístěn ve státě, byla zrušena a modul runtime zahodí všechny úkoly, které dosud nebyly zahájeny.Další informace o zpracování výjimek a paralelní algoritmy, viz Zpracování výjimek v souběžném běhu.

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

[!POZNÁMKA]

Plánování nákladů, že výsledky z zátěže a podporu funkcí, jako je například zrušení nemusí překonat výhody spuštění smyčky jejíž tělo paralelně, zvláště když smyčky jejíž tělo je relativně malé.Toto zatížení lze minimalizovat pomocí rozdělovač v paralelní smyčka.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 algoritmus.Tento příklad vytiskne konzolu pro 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í výstup:

Protože parallel_for algoritmus funguje u každé položky v paralelní, pořadí tisku hodnoty ke konzole může být různý.

Kompletní příklad, který používá parallel_for algoritmus, viz Postup: zápis parallel_for smyčka.

Top

Parallel_for_each algoritmus

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

parallel_for_each Algoritmus se podobá STL std::for_each algoritmus, s výjimkou případů, které parallel_for_each algoritmus provede úkolů současně.Stejně jako ostatní paralelní algoritmy, parallel_for_each nespustí úkoly v určitém pořadí.

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

Příklad

Následující příklad zobrazuje základní strukturu parallel_for_each algoritmus.Tento příklad vytiskne konzolu pro každou hodnotu std::array objekt 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), begin(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

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

Protože parallel_for_each algoritmus funguje u každé položky v paralelní, pořadí tisku hodnoty ke konzole může být různý.

Kompletní příklad, který používá parallel_for_each algoritmus, viz Postup: zápis parallel_for_each smyčka.

Top

Parallel_invoke algoritmus

Concurrency::parallel_invoke algoritmus provede několik úkolů současně.Nevrací se až do dokončení každého úkolu.Tento algoritmus je užitečné, pokud máte několik nezávislých úkolů, které má být proveden ve stejnou dobu.

parallel_invoke Algoritmus bere jako její parametry řadu pracovních funkcí (lambda funkce, funkce objektů nebo ukazatele na funkci).parallel_invoke Algoritmus je přetížena vzít mezi dvěma a deset parametry.Každá funkce, který předáte parallel_invoke musí být nulové parametry.

Stejně jako ostatní paralelní algoritmy, parallel_invoke nespustí úkoly v určitém pořadí.Téma Úkol rovnoběžnosti (souběžnosti Runtime) vysvětluje, jak se parallel_invoke algoritmus se týká úkolů a skupin úkolů.

Příklad

Následující příklad zobrazuje základní strukturu parallel_invoke algoritmus.V tomto příkladu souběžně volá 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 Postup: zápis paralelní rutinní řazení pomocí parallel_invoke a Jak: použití parallel_invoke k provedení paralelní operace.

Top

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 není určeno pořadí operace, protože jsou prováděny paralelně.Tyto algoritmy se používají při práci se sadou, která je dostatečně velká, chcete-li získat výhody výkonu a škálovatelnosti z paralelní zpracování.

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

Parallel_transform algoritmus

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

• Upravit jas obrazu a provádění dalších operací zpracování obrazu.

• Sečíst, nebo přijmout produkt tečkou mezi dva vektory a provádět jiné číselné výpočty vektorů.

• Provádějte trasování 3D ray, kde každé iteraci odkazuje na jeden pixel, který musí být vykreslen.

Následující příklad ukazuje základní strukturu, která je použita k volání parallel_transform algoritmus.V tomto příkladu Neguje každý prvek std::vector objekt dvěma způsoby.První způsob využívá lambda výraz.Druhý způsob využívá std::negate, který je odvozen 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 základní použití parallel_transform.Protože funkce práce neprovádí značné množství práce, nelze očekávat výrazné zvýšení výkonu v tomto příkladu.

parallel_transform Algoritmus má dvě přetížení.První přetížení přijímá jeden vstupní oblasti a funkce unární.Unární funkce může být lambda výraz, který přijímá jeden argument, funkce objektu nebo typ, který je odvozen z unary_function.Druhý přetížení přijímá dvě 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 z 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, kterou zadáte pro výstup parallel_transform musí zcela překrývají vstupní iterátor nebo vůbec nebudou překrývat.Chování tohoto algoritmu nezadané, pokud iterátorů vstupní a výstupní se částečně překrývají.

Parallel_reduce algoritmus

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

• Násobení řad matice k matici.

• Vynásobte vektor posloupnost matric pro vytvoření vektoru.

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

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

Následující základní příklad ukazuje, jak použít parallel_reduce algoritmus kombinovat posloupnosti řetězců do jednoho řetězce.Stejně jako příklady pro parallel_transform, nejsou v této základní příklad očekáván 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 lze považovat parallel_reduce jako zkratku pro použití parallel_for_each algoritmus společně s concurrency::combinable třídy.

Příklad: Provádění mapování a snížit paralelně

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

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

// 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 snížit operace paralelně, viz Jak: provést mapování a snížit operace paralelně.

Top

Rozdělení práce

Paralelizovat 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áken.Rozdělovač Určuje, jak by měl paralelního algoritmu oddílů oblastí mezi vlákny.Jak je popsáno dříve v tomto dokumentu, PPL používá výchozí oddíly mechanismus, který vytvoří počáteční zatížení a potom pomocí práce krást algoritmus a rozsah krást vyvážit tyto oddíly při zatížení nevyrovnané.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ě.Pro některé scénáře, můžete však 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é verze, které přijímají parametr Další _Partitioner.Tento parametr definuje typ rozdělovač, který rozděluje práci.Zde jsou druhy rozdělovače, které definuje PPL:

• Concurrency::affinity_partitioner
  Rozdělí se práce 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 rozsahy pracovních podprocesů.Tento typ rozdělovač může zvýšit výkon při spuštění smyčky přes stejnou sadu dat několikrát (například smyčky uvnitř smyčky) a data vejdou do mezipaměti.Tento rozdělovač zrušení plně neúčastní.Také nepoužívá spolupráce blokování sémantiky a proto jej nelze použít s paralelní smyčky, které mají závislost vpřed.

• Concurrency::auto_partitioner
  Rozdělí se práce 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á tento typ ve výchozím nastavení při volání nejsou přetížené paralelního algoritmu, který přijímá _Partitioner parametr.Každý rozsah lze rozdělit na sub-ranges a tím umožňuje zatížení dochází.Po dokončení rozsah práce Redistribuuje modul runtime sub-ranges práce z jiných vláken na tomto vlákně.Tento rozdělovač použijte v případě, že vaše pracovní vytížení nespadá pod jedním z 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 není rozdělení oblastí do sub-ranges.Pro každého zaměstnance, modul runtime hledá zrušení a provádí vyrovnávání zatížení po _Chunk_size dokončení iterací.

• Concurrency::static_partitioner
  Rozdělí se práce 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ůžete zlepšit výkon, protože nepoužívá krást práce a proto má menší režii.Pomocí tohoto typu rozdělovač při každé iteraci paralelní smyčka provádí pevné a jednotné 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é iterátorů náhodný přístup (jako například std::vector) pro statické, jednoduchá a spřažení rozdělovače.Použití kontejnery, které obousměrné a dopředu iterátorů způsobil chybu kompilace.Výchozí rozdělovač auto_partitioner, podporuje všechny tři typy iterátoru.

Obvykle se používají tyto rozdělovače 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í předat affinity_partitioner objekt jako než-const, l hodnota odkazovat tak, že algoritmus lze ukládat stav pro budoucí smyčky pro opakované použití.Následující příklad ukazuje základní aplikace, která provádí stejné operace v množině 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;

int wmain()
{    
    // Create an arry and fill it with zeroes.
    array<unsigned char, 8 * 1024> data;
    data.fill(0);

    //
    // Use an affinity partitioner to perform parallel work on data
    // that is likely to remain in cache.
    // We use the same affinitiy partitioner throughout so that the 
    // runtime can schedule work to occur at the same location for each 
    // iteration of the outer loop.

    affinity_partitioner ap;
    for (int i = 0; i < 100000; i++)
    {        
        parallel_for_each(begin(data), end(data), [](unsigned char& c) {
            c++;
        }, ap);
    }
}

Upozornění
Buďte opatrní při úpravě existující kód, který se opírá o kooperativní blokování sémantiku pomocí static_partitioner nebo affinity_partitioner.Tyto typy rozdělovač nepoužívejte zátěže nebo rozsah krást a proto může dojít ke změně chování aplikace.

Nejlepší způsob, jak určit, zda použít rozdělovač v jakýkoli daný scénář je experimentovat a změřit, jak dlouho trvá operace dokončena za reprezentativní zatížení a konfigurací počítače.Například statické rozdělení do oddílů může poskytnout významné možné příliš zrychlit vícejádrové počítače, který má pouze několik jádra, ale může dojít k zpomalování v počítačích s relativně mnoho jader.

Top

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é, když máte sadu dat, která mohou mít prospěch z řazen paralelně.Zejména řazení paralelně je užitečné Pokud máte velké datové sady nebo použijete-li porovnat výpočetně náročné operace řazení dat.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á, že jejich porovnat prvky podle hodnoty.parallel_sort Algoritmus 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á, že používá celé číslo klíče řazení prvků.Pomocí klávesy lze tento algoritmus výpočtu přímo cílový element namísto použití porovnávání.Stejně jako parallel_buffered_sort, vyžaduje tento algoritmus O(N) místa.

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

Algoritmus	Description	Mechanismus řazení	Stabilitě řazení	Požadavky na paměť	Složitost čas	Přístup iterátor
parallel_sort	Univerzální řazení na základě 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í ilustrace znázorňuje důležité vlastnosti tři paralelní algoritmy řazení více graficky.

Tyto paralelní řazení algoritmy se řídí pravidly o 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 souběžném běhu.

Tip

Tyto paralelní řazení algoritmy podporují sémantiky přesunutí.Můžete definovat operátor přiřazení přesunout, chcete-li povolit odkládací operací efektivněji.Další informace o přesunutí sémantiky a operátor přiřazení přesunout, viz Rvalue referenční Declarator: & &, a Jak: Zapsat přesun konstruktor.Pokud nezadáte přesunout operátoru nebo funkce, odkládací, algoritmy řazení pomocí kopie konstruktoru.

Následující základní příklad zobrazuje způsob použití parallel_sort Chcete-li seřadit 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 metodu řazení std::complex <double> 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 funkci hash parallel_radixsort algoritmus.V tomto příkladu seřadí 3D body.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 tento příklad používá poměrně malých sad dat.Počáteční velikost vektoru experimentovat s výkonu přes větší sady dat, můžete zvýšit.

Tento příklad používá lambda výraz jako funkci hash.Můžete také použít jednu z předdefinované implementace std::hash třídou nebo definovat vlastní specializace.Objekt vlastní hash funkce můžete také tak, 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).Tato integrálního typu musí být převoditelný na zadejte size_t.

Volba třídění algoritmus

V mnoha případech parallel_sort poskytuje nejlepší vyvážení rychlosti a paměti výkon.Však jako můžete zvětšit velikost množiny dat, počet dostupných procesorů nebo složité funkce compare, parallel_buffered_sort nebo parallel_radixsort může fungovat rychleji.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á řazení dat typických za reprezentativní konfiguraci počítače.Pokud zvolíte řazení strategie mějte na paměti následující pokyny.

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

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

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

• Vlastnosti sady dat.Jeden algoritmus může být například provést 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 se algoritmus přepne z paralelní implementace pořadové řazení tak, 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í při 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 paralelně.

Nemusí být výrazné zlepšení řazení malé dataset paralelně, i když máte velký počet dostupných výpočetních prostředků nebo porovnání funkce nebo funkci 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 volání sort je-li zadat velikost bloku, který je větší než je objekt dataset; Nicméně parallel_buffered_sort musel přidělit O(N) prostor, což může trvat déle, z důvodu sporu nebo paměti přidělení zámku.)

Je-li nutné šetřit paměť nebo váš modul pro přidělování paměti je zámků, použijte parallel_sort řazení střední objektu 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.parallel_buffered_sortmůže být užitečné, když máte velký počet výpočetních prostředků nebo nákladné porovnání funkce či funkce hash.

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

Upozornění
Implementace Kvalitní zatřiďovací funkce je třeba znát rozsah objektu dataset a jak je každý element v objektu dataset transformován do odpovídající hodnota bez znaménka.Protože operace hash pracuje na nepodepsané hodnoty, zvažte různé strategie řazení, je-li nepodepsaný 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 stejné rozsáhlé sady 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 provede nejlepší u tohoto objektu dataset v této konfiguraci počítače.

Top

Příbuzná témata

Title	Description
Postup: zápis parallel_for smyčka	Ukazuje, jak použít parallel_for algoritmus k provedení násobení matice.
Postup: zápis parallel_for_each smyčka	Ukazuje, jak použít parallel_for_each algoritmus výpočtu počtu prvočísel v std::array objekt paralelně.
Postup: zápis paralelní rutinní řazení pomocí parallel_invoke	Ukazuje, jak použít parallel_invoke algoritmus pro zlepšení výkonu řadicí algoritmus bitonic.
Jak: použití parallel_invoke k provedení paralelní operace	Ukazuje, jak použít parallel_invoke algoritmus pro zlepšení výkonu programu, který provádí více operací na sdílené datové zdroje.
Jak: provést mapování a snížit operace paralelně	Ukazuje, jak použít parallel_transform a parallel_reduce algoritmy mapu a zmenšit operace, která spočítá výskyty slova v souborech.
Paralelní knihovnu vzorků (PPL)	Popisuje PPL, která poskytuje imperativní programovací model, který podporuje škálovatelnost a použití pro vývoj aplikací pro souběžné.
Zrušení v 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 souběžném běhu	Vysvětluje roli zpracování výjimek v modulu Runtime souběžnosti.

Odkaz

parallel_for funkce

parallel_for_each funkce

parallel_invoke funkce

Třída affinity_partitioner

Třída auto_partitioner

Třída simple_partitioner

Třída static_partitioner

parallel_sort funkce

parallel_buffered_sort funkce

parallel_radixsort funkce