Párhuzamos algoritmusok

A párhuzamos minták kódtára (PPL) olyan algoritmusokat biztosít, amelyek egyidejűleg végeznek munkát az adatgyűjteményeken. Ezek az algoritmusok a C++ standard kódtár által biztosított algoritmusokhoz hasonlítanak.

A párhuzamos algoritmusok az egyidejűségi futtatókörnyezet meglévő funkcióiból állnak. Az egyidejűség::parallel_for algoritmus például egy egyidejűség::structured_task_group objektumot használ a párhuzamos ciklus iterációinak végrehajtásához. Az parallel_for algoritmuspartíciók optimális módon működnek a rendelkezésre álló számítási erőforrások száma alapján.

Szakaszok

• Parallel_for algoritmus

• A Parallel_for_each algoritmus

• A parallel_invoke algoritmus

• A parallel_transform és parallel_reduce algoritmusok

  • A parallel_transform algoritmus

  • A parallel_reduce algoritmus

  • Példa: Leképezés és csökkentés végrehajtása párhuzamosan

• Particionálási munka

• Párhuzamos rendezés

  • Rendezési algoritmus kiválasztása

A parallel_for algoritmus

Az concurrency::parallel_for algoritmus ismételten ugyanazt a feladatot hajtja végre párhuzamosan. Ezek a tevékenységek egy iterációs értékkel vannak paraméterezve. Ez az algoritmus akkor hasznos, ha olyan ciklustörzse van, amely nem oszt meg erőforrásokat a ciklus iterációi között.

Az parallel_for algoritmus optimális módon particionálja a feladatokat a párhuzamos végrehajtáshoz. Munkalopó algoritmust és tartománylopást használ a partíciók kiegyensúlyozása érdekében, ha a számítási feladatok kiegyensúlyozatlanok. Amikor egy iteráció kooperatív módon blokkol egy hurkot, a futtatási környezet újraosztja az aktuális szálhoz rendelt iterációk tartományát más szálakra vagy processzorokra. Hasonlóképpen, amikor egy szál befejez egy iterációs tartományt, a futtatókörnyezet átosztja a munkát más szálakról erre a szálra. Az parallel_for algoritmus támogatja a beágyazott párhuzamosságot is. Ha egy párhuzamos hurok egy másik párhuzamos hurkot tartalmaz, a futtatókörnyezet hatékonyan koordinálja az erőforrások feldolgozását a ciklustestek között a párhuzamos végrehajtás érdekében.

Az parallel_for algoritmus több túlterhelt verzióval rendelkezik. Az első verzió egy kezdőértéket, egy végértéket és egy munkafüggvényt (lambda kifejezést, függvényobjektumot vagy függvénymutatót) vesz igénybe. A második verzió egy kezdőértéket, egy végértéket, egy lépéshez szükséges értéket és egy munkafüggvényt vesz fel. A függvény első verziója 1-et használ lépésértékként. A fennmaradó verziók particionáló objektumokat vesznek fel, amelyek segítségével megadhatja, hogyan parallel_for kell particionálási tartományokat létrehozni a szálak között. A particionálókat részletesebben a dokumentum Particionálási munka című szakasza ismerteti.

Számos for hurkot átalakíthat a parallel_for használatához. Az parallel_for algoritmus azonban a következő módokon tér el az for utasítástól:

• Az parallel_for algoritmus parallel_for nem hajtja végre előre meghatározott sorrendben a feladatokat.

• Az parallel_for algoritmus nem támogatja az tetszőleges felmondási feltételeket. Az parallel_for algoritmus leáll, ha az iterációs változó aktuális értéke eggyel kisebb, mint last.

• A _Index_type típusparaméternek szerves típusnak kell lennie. Ez az integráltípus aláírható vagy aláíratlan.

• A hurok iterációjának előre kell irányulnia. Az parallel_for algoritmus kivételt ad az std::invalid_argument típustól, ha a _Step paraméter 1-nél kisebb.

• Az algoritmus kivételkezelési mechanizmusa parallel_for eltér a for hurkoktól. Ha egyszerre több kivétel is előfordul egy párhuzamos hurok törzsében, a futtatókörnyezet csak az egyik kivételt propagálja a hívott parallel_forszálra. Emellett, ha egy ciklus iteráció kivételt okoz, a futtatókörnyezet nem állítja le azonnal a teljes ciklust. Ehelyett a ciklus megszakított állapotba kerül, és a futtatókörnyezet elveti azokat a tevékenységeket, amelyek még nem kezdődtek el. A kivételkezeléssel és a párhuzamos algoritmusokkal kapcsolatos további információkért lásd: Kivételkezelés.

Bár az parallel_for algoritmus nem támogatja az tetszőleges leállítási feltételeket, a lemondással leállíthatja az összes feladatot. További információ a lemondásról: Lemondás a PPL-ben.

Megjegyzés:

A terheléselosztásból és az olyan funkciók támogatásából eredő ütemezési költségek, mint például a törlés, esetleg nem egyenlítik ki a ciklus törzsének párhuzamos végrehajtásából származó előnyöket, különösen akkor, ha a ciklus törzse viszonylag kicsi. Ezt a többletterhelést minimalizálhatja egy particionálóval a párhuzamos hurokban. További információ: Particionálási munka a dokumentum későbbi részében.

példa

Az alábbi példa az algoritmus alapstruktúráját parallel_for mutatja be. Ez a példa a konzolra nyomtatja az [1, 5] tartomány minden értékét párhuzamosan.

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

Ez a példa a következő mintakimenetet hozza létre:

1 2 4 3 5

Mivel az parallel_for algoritmus párhuzamosan működik az egyes elemeken, az értékek konzolra való nyomtatásának sorrendje eltérő lesz.

A parallel_for algoritmus alkalmazására vonatkozó teljes példát lásd a következő útmutatóban: Hogyan írjunk parallel_for hurkot?.

[Felső]

A Parallel_for_each algoritmus

Az concurrency::parallel_for_each algoritmus egy iteráló tárolón hajt végre feladatokat párhuzamosan, például a C++ Standard Könyvtár által biztosítottakon. Ugyanazt a particionálási logikát használja, amelyet az parallel_for algoritmus használ.

Az parallel_for_each algoritmus a C++ Standard Library std::for_each algoritmushoz hasonlít, azzal a kivételével, hogy az parallel_for_each algoritmus egyszerre hajtja végre a feladatokat. A többi párhuzamos algoritmushoz parallel_for_each hasonlóan nem hajtja végre a feladatokat egy adott sorrendben.

Bár az parallel_for_each algoritmus a továbbítási iterátorokon és a véletlenszerű hozzáférési iterátorokon is működik, a véletlenszerű hozzáférés iterátoraival jobban teljesít.

példa

Az alábbi példa az algoritmus alapstruktúráját parallel_for_each mutatja be. Ez a példa egy std::tömbobjektum minden értékét párhuzamosan nyomtatja a konzolra.

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

Ez a példa a következő mintakimenetet hozza létre:

4 5 1 2 3

Mivel az parallel_for_each algoritmus párhuzamosan működik az egyes elemeken, az értékek konzolra való nyomtatásának sorrendje eltérő lesz.

A parallel_for_each algoritmust használó teljes példa megtekintéséhez lásd: Útmutató: Parallel_for_each hurok írása.

[Felső]

A "parallel_invoke" algoritmus

A concurrency::parallel_invoke algoritmus párhuzamosan hajt végre egy csoport feladatot. Nem tér vissza, amíg az egyes tevékenységek be nem fejeződnek. Ez az algoritmus akkor hasznos, ha több független feladatot szeretne egyszerre végrehajtani.

Az parallel_invoke algoritmus paraméterekként több munkafüggvényt (lambdafüggvényeket, függvényobjektumokat vagy függvénymutatókat) vesz fel. A parallel_invoke algoritmus túl van terhelve úgy, hogy két és tíz paramétert is el tud fogadni. Minden átadott függvénynek parallel_invoke nulla paramétert kell megadnia.

A többi párhuzamos algoritmushoz parallel_invoke hasonlóan nem hajtja végre a feladatokat egy adott sorrendben. A Feladat-párhuzamosság témakör ismerteti, hogyan kapcsolódik az algoritmus a parallel_invoke tevékenységekhez és a tevékenységcsoportokhoz.

példa

Az alábbi példa az algoritmus alapstruktúráját parallel_invoke mutatja be. Ez a példa egyszerre hívja meg a twice függvényt három helyi változón, és kinyomtatja az eredményt a konzolon.

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

Ez a példa a következő kimenetet hozza létre:

108 11.2 HelloHello

Az algoritmust használó teljes példákra lásd: parallel_invoke és Hogyan lehet parallel_invoke használatával párhuzamos műveleteket végrehajtani.

[Felső]

A parallel_transform és parallel_reduce algoritmusok

A concurrency::parallel_transform és concurrency::parallel_reduce algoritmusok a C++ Standard Library algoritmusok párhuzamos verziói, azaz a std::transform és a std::accumulate. Az egyidejűségi futtatókörnyezet verziói úgy viselkednek, mint a C++ standard kódtár verziói, azzal a kivétellel, hogy a műveleti sorrend nem határozható meg, mert párhuzamosan futnak. Ezeket az algoritmusokat akkor használja, ha olyan készlettel dolgozik, amely elég nagy ahhoz, hogy a teljesítmény és a méretezhetőség előnyeit kihasználja a párhuzamos feldolgozás.

Fontos

Az parallel_transform és parallel_reduce az algoritmusok csak a véletlenszerű hozzáférést, a kétirányú és a továbbítási iterátorokat támogatják, mivel ezek az iterátorok stabil memóriacímeket hoznak létre. Emellett ezeknek az iterátoroknak nemconst l-értékeket kell előállítaniuk.

A Parallel_transform algoritmus

Az parallel transform algoritmussal számos adat párhuzamosítási műveletet hajthat végre. Például megteheted a következőket:

• Állítsa be a kép fényerejét, és végezzen más képfeldolgozási műveleteket.

• A pont szorzatát összeadhatja két vektor között, és más numerikus számításokat végezhet a vektorokon.

• Végezze el a térhatású sugárkövetést, ahol minden iteráció egy képpontra hivatkozik, amelyet renderelni kell.

Az alábbi példa az algoritmus meghívására használt alapstruktúrát parallel_transform mutatja be. Ez a példa két módon tagadja meg az std::vector objektum minden elemét. Az első módszer egy lambda kifejezést használ. A második módszer az std::negate függvényt használja, amely az std::unary_function függvényből származik.

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

Figyelmeztetés

Ez a példa a parallel_transform alapvető használatát mutatja be. Mivel a munkafüggvény nem végez jelentős mennyiségű munkát, ebben a példában nem várható jelentős teljesítménynövekedés.

Az parallel_transform algoritmusnak két túlterhelése van. Az első túlterhelés egy bemeneti tartományt és egy unary függvényt vesz igénybe. A unary függvény lehet egy lambda kifejezés, amely egy argumentumot, egy függvényobjektumot vagy egy olyan típust vesz igénybe, amelyből származik unary_function. A második túlterhelés két bemeneti tartományt és egy bináris függvényt vesz igénybe. A bináris függvény lehet lambda kifejezés, amely két argumentumot, egy függvényobjektumot vagy egy std::binary_function függvényből származó típust vesz igénybe. Az alábbi példa ezeket a különbségeket szemlélteti.

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

Fontos

A kimenethez parallel_transform megadott iterátornak teljesen át kell fednie a bemeneti iterátort, vagy egyáltalán nem fedheti át. Az algoritmus viselkedése meghatározatlan, ha a bemeneti és kimeneti iterátorok részben átfedésben vannak.

A parallel_reduce algoritmus

Az parallel_reduce algoritmus akkor hasznos, ha olyan műveletek sorozatával rendelkezik, amelyek megfelelnek az asszociatív tulajdonságnak. (Ehhez az algoritmushoz nincs szükség a kommutatív tulajdonságra.) Íme néhány olyan művelet, amelyet parallel_reduce segítségével hajthat végre:

• Mátrixok sorozatainak szorzása mátrix létrehozásához.

• Vektor szorzása mátrixok sorozatával vektor előállításához.

• Sztringsorozat hosszának kiszámítása.

• Például sztringek listáját kombinálja egyetlen elemmé.

Az alábbi egyszerű példa bemutatja, hogyan használható az parallel_reduce algoritmus egy karakterlánc-sorozat egyetlen karakterlánccá való egyesítésére. A példákhoz parallel_transformhasonlóan ebben az alap példában sem várható teljesítménynövekedés.

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

Az parallel_reduce sok esetben a parallel_for_each algoritmus és a concurrency::combinable osztály használatának rövidítéseként is felfogható.

Példa: Leképezés és csökkentés végrehajtása párhuzamosan

A leképezési művelet függvényt alkalmaz a sorozat minden értékére. A csökkentési művelet egy sorozat elemeit egyetlen értékre egyesíti. A C++ Standard Library std::transform and std::accumulate függvények használatával térkép- és csökkentési műveleteket hajthat végre. Számos probléma esetén azonban az parallel_transform algoritmus használatával párhuzamosan hajthatja végre a leképezési műveletet, az parallel_reduce algoritmus pedig párhuzamosan hajtja végre a csökkentési műveletet.

Az alábbi példa összehasonlítja a prímszámok összegének soros és párhuzamos kiszámításához szükséges időt. A leképezési fázis 0-ra alakítja át a nem elsődleges értékeket, a csökkentési fázis pedig összegzi az értékeket.

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

A térképet és a csökkentési műveletet párhuzamosan végrehajtó másik példa : Útmutató: Leképezési és csökkentési műveletek párhuzamos végrehajtása.

[Felső]

Particionálási munka

Egy adatforráson végzett művelet párhuzamossá alakításához alapvető lépés a forrás több szakaszra való particionálása , amely egyszerre több szálon keresztül is elérhető. Egy particionáló meghatározza, hogy a párhuzamos algoritmus hogyan osztja fel a tartományokat a szálak között. A dokumentumban korábban ismertetett módon a PPL egy alapértelmezett particionálási mechanizmust használ, amely létrehoz egy kezdeti számítási feladatot, majd egy munkalopási algoritmussal és tartománylopással egyensúlyba hozza ezeket a partíciókat, amikor a számítási feladatok kiegyensúlyozatlanok. Például, amikor egy ciklus iterációja több iterációt fejez be, a futtatókörnyezet átrendezi a munkát a többi szálról az adott szálra. Egyes forgatókönyvek esetében azonban érdemes lehet egy másik particionálási mechanizmust megadni, amely jobban megfelel a problémának.

A parallel_for, parallel_for_eachés parallel_transform az algoritmusok túlterhelt verziókat biztosítanak, amelyek egy további paramétert _Partitionervesznek igénybe. Ez a paraméter határozza meg a munkát megosztó particionáló típusát. A PPL az alábbi partíciótípusokat határozza meg:

egyidejűség::hozzárendelési_particionáló
A munkát rögzített számú tartományra osztja (általában a cikluson való munkavégzéshez rendelkezésre álló munkaszálak számát). Ez a particionálótípus hasonlít a static_partitioner típusra, de úgy javítja a gyorsítótár-affinitást, hogy a tartományokat a feldolgozó szálakhoz rendeli. Ez a particionálótípus javíthatja a teljesítményt, ha egy hurkot többször hajtanak végre ugyanazon adatkészleten (például egy cikluson belüli hurokon), és az adatok elférnek a gyorsítótárban. Ez a particionáló nem vesz teljes mértékben részt a megszakításban. Nem használ kooperatív blokkoló szemantikát, ezért nem használható olyan párhuzamos hurkokkal, amelyek továbbítási függőséggel rendelkeznek.

egyidejűség::auto_partitioner
A munkát egy kezdeti számú tartományra osztja (ami általában megegyezik a cikluson dolgozó elérhető munkaszálak számával). A futtatókörnyezet alapértelmezés szerint ezt a típust használja, ha nem hív meg túlterhelt párhuzamos algoritmust, amely paramétert _Partitioner használ. Minden tartomány altartományokra osztható, így lehetővé teszi a terheléselosztást. Amikor egy munkatartomány befejeződik, a futtatókörnyezet újra elosztja a munka altartományait más szálaktól az adott szálig. Ezt a particionálót akkor használja, ha a számítási feladat nem tartozik a többi kategória egyikébe, vagy teljes körű támogatást igényel a lemondáshoz vagy a kooperatív blokkoláshoz.

egyidejűség::simple_partitioner
Olyan tartományokra osztja a munkát, amelyekben minden tartomány legalább az adott adattömbméret által megadott iterációk számát tartalmazza. Ez a particionálótípus részt vesz a terheléselosztásban; a futtatókörnyezet azonban nem osztja el a tartományokat altartományokra. Minden egyes feldolgozó esetében a futtatókörnyezet ellenőrzi a lemondást, és az iterációk befejezése után _Chunk_size elvégzi a terheléselosztást.

egyidejűség::static_partitioner
A munkát rögzített számú tartományra osztja (általában a cikluson való munkavégzéshez rendelkezésre álló munkaszálak számát). Ez a particionálótípus javíthatja a teljesítményt, mivel nem használ munkalopást, ezért kisebb a terhelése. Ezt a particionálótípust akkor használja, ha egy párhuzamos ciklus minden iterációja rögzített és egységes munkamennyiséget végez, és nem igényel támogatást a lemondáshoz vagy a kooperatív blokkolás továbbításához.

Figyelmeztetés

Az parallel_for_each és parallel_transform az algoritmusok csak olyan tárolókat támogatnak, amelyek véletlenszerű hozzáférési iterátorokat (például std::vector) használnak a statikus, az egyszerű és az affinitásparticionálókhoz. A kétirányú és előre mutató iterátorokat használó tárolók fordítási idejű hibát eredményeznek. Az alapértelmezett particionáló auto_partitionermindhárom iterátortípust támogatja.

Ezeket a particionálókat általában ugyanúgy használják, kivéve a affinity_partitioner. A legtöbb particionálótípus nem tartja karban az állapotot, és a futtatókörnyezet nem módosítja. Ezért ezeket a particionáló objektumokat a hívási helyen hozhatja létre, ahogyan az az alábbi példában is látható.

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

Az objektumot azonban nem l-értékaffinity_partitioner hivatkozásként kell átadniaconst, hogy az algoritmus a jövőbeli ciklusok állapotát újra felhasználhassa. Az alábbi példa egy olyan alapszintű alkalmazást mutat be, amely ugyanazt a műveletet többször hajtja végre egy adathalmazon párhuzamosan. A affinity_partitioner használata javíthatja a teljesítményt, mert a tömb valószínűleg elfér a gyorsítótárban.

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

Figyelmeztetés

Óvatosan járjon el, amikor módosítja a meglévő kódot, amely kooperatív blokkoló szemantikára támaszkodik, hogy static_partitioner vagy affinity_partitioner használatát alkalmazza. Ezek a particionálótípusok nem használnak terheléselosztást vagy tartománylopásokat, ezért megváltoztathatják az alkalmazás viselkedését.

Annak meghatározására, hogy egy adott forgatókönyvben használ-e particionálót, a legjobb módszer a kísérletezés és annak mérése, hogy mennyi ideig tart a műveletek végrehajtása reprezentatív terhelések és számítógép-konfigurációk esetén. A statikus particionálás például jelentős felgyorsulást okozhat egy többmagos számítógépen, amely csak néhány maggal rendelkezik, de a viszonylag sok maggal rendelkező számítógépeken lassulást eredményezhet.

[Felső]

Párhuzamos rendezés

A PPL három rendezési algoritmust biztosít: concurrency::parallel_sort, concurrency::parallel_buffered_sort és concurrency::parallel_radixsort. Ezek a rendezési algoritmusok akkor hasznosak, ha olyan adatkészlettel rendelkezik, amely kihasználhatja a párhuzamos rendezés előnyeit. A párhuzamos rendezés különösen akkor hasznos, ha nagy adatkészlettel rendelkezik, vagy ha számítással költséges összehasonlítási műveletet használ az adatok rendezéséhez. Ezen algoritmusok mindegyike a helyén rendezi az elemeket.

Az parallel_sort és a parallel_buffered_sort algoritmusok egyaránt összehasonlításalapú algoritmusok. Vagyis érték szerint hasonlítják össze az elemeket. Az parallel_sort algoritmus nem rendelkezik további memóriakövetelményekkel, és általános célú rendezésre alkalmas. Az parallel_buffered_sort algoritmus jobb teljesítményt nyújt, mint parallel_sort, de O(N) szóközt igényel.

Az parallel_radixsort algoritmus kivonatalapú. Vagyis egész számbillentyűkkel rendezi az elemeket. A kulcsok használatával ez az algoritmus közvetlenül kiszámíthatja egy elem célját összehasonlítások helyett. Ehhez az algoritmushoz parallel_buffered_sort hasonlóan O(N) tárhelyre van szükség.

Az alábbi táblázat a három párhuzamos rendezési algoritmus fontos tulajdonságait foglalja össze.

Algoritmus	Leírás	Rendezési mechanizmus	Stabilitás rendezése	Memóriakövetelmények	Az idő összetettsége	Iterátor-hozzáférés
parallel_sort	Általános célú összehasonlításalapú rendezés.	Összehasonlításalapú (növekvő)	Instabil	Egyik sem	O((N/P)log(N/P) + 2N((P-1)/P))	Véletlenszerű
parallel_buffered_sort	Gyorsabb, általános célú összehasonlításalapú rendezés, amely O(N) tárhelyet igényel.	Összehasonlításalapú (növekvő)	Instabil	További O(N) memória szükséges	O((N/P)log(N))	Véletlenszerű
parallel_radixsort	Egész szám alapú kulcs szerinti rendezés, amely O(N) méretű memóriát igényel.	Kivonatalapú	Stabil	További O(N) memória szükséges	O(N/P)	Véletlenszerű

Az alábbi ábrán a három párhuzamos rendezési algoritmus lényeges tulajdonságai láthatók grafikusabban.

Ezek a párhuzamos rendezési algoritmusok a lemondás és a kivételkezelés szabályait követik. Az egyidejűségi futtatókörnyezet lemondásával és kivételkezelésével kapcsolatos további információkért lásd: Párhuzamos algoritmusok megszakítása és kivételkezelés.

Jótanács

Ezek a párhuzamos rendezési algoritmusok támogatják az átvitel szemantikáját. Az áthelyezés-hozzárendelési operátort úgy határozhatja meg, hogy a felcserélési műveletek hatékonyabbak legyenek. Az áthelyezési szemantikáról és az áthelyezési hozzárendelés-operátorról további információt az Rvalue Reference Deklarátor: && és a Move konstruktorok és Move hozzárendelési operátorok (C++) című oldalakban találhatók. Ha nem biztosít áthelyezési hozzárendelési operátort vagy felcserélési függvényt, a rendezési algoritmusok a másolási konstruktort használják.

Az alábbi egyszerű példa bemutatja, hogyan használhatja a parallel_sort-t vector értékekből álló int rendezésére. Alapértelmezés szerint parallel_sort az std::less használatával hasonlítja össze az értékeket.

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

Ez a példa bemutatja, hogyan adhat meg egyéni összehasonlítási függvényt. Az std::complex:real metódussal rendezi az std::komplex<kettős> értékeket növekvő sorrendben.

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

Ez a példa bemutatja, hogyan biztosíthat kivonatfüggvényt az parallel_radixsort algoritmusnak. Ez a példa 3D pontokat rendez. A pontok a referenciaponttól való távolságuk alapján vannak rendezve.

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

Illusztrációként ez a példa egy viszonylag kis adatkészletet használ. A vektor kezdeti méretének növelésével nagyobb adatkészletek teljesítménybeli javulásával kísérletezhet.

Ez a példa egy lambda kifejezést használ kivonatfüggvényként. Használhatja az std::hash osztály egyik beépített implementációját is, vagy meghatározhatja saját specializációját. Egyéni hash-függvény-objektumot is használhat, ahogyan az ebben a példában látható:

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

A kivonatoló függvénynek egy integráltípust kell visszaadnia (std::is_integral::értéknek kell lennie true). Ennek az integráltípusnak átalakíthatónak kell lennie típussá size_t.

Rendezési algoritmus kiválasztása

Sok esetben parallel_sort a sebesség és a memória teljesítményének legjobb egyensúlyát biztosítja. Ha azonban növeli az adatkészlet méretét, az elérhető processzorok számát vagy az összehasonlítási függvény összetettségét, parallel_buffered_sort vagy parallel_radixsort jobban teljesít. A legjobb módszer annak meghatározására, hogy melyik rendezési algoritmust kell használni egy adott forgatókönyvben, ha kísérletezik és méri, hogy mennyi ideig tart a tipikus adatok rendezése reprezentatív számítógép-konfigurációk szerint. A rendezési stratégia kiválasztásakor tartsa szem előtt az alábbi irányelveket.

• Az adatkészlet mérete. Ebben a dokumentumban egy kis adatkészlet kevesebb mint 1000 elemet, egy közepes adatkészlet 10 000 és 100 000 elemet tartalmaz, egy nagy adatkészlet pedig több mint 100 000 elemet tartalmaz.

• Az összehasonlítási függvény vagy kivonatfüggvény által végzett munka mennyisége.

• A rendelkezésre álló számítási erőforrások mennyisége.

• Az adathalmaz jellemzői. Egy algoritmus például jól teljesít a már majdnem rendezett adatok esetében, de nem olyan jól, mint a teljesen rendezetlen adatok esetében.

• Az adattömb mérete. Az opcionális _Chunk_size argumentum azt határozza meg, hogy az algoritmus mikor vált át párhuzamosról soros rendezési implementációra, mivel az a teljes rendezést kisebb munkaegységekre alakítja. Ha például 512-et ad meg, az algoritmus akkor vált soros implementációra, ha egy munkaegység 512 vagy kevesebb elemet tartalmaz. A soros implementáció javíthatja az általános teljesítményt, mivel kiküszöböli az adatok párhuzamos feldolgozásához szükséges többletterhelést.

Előfordulhat, hogy nem érdemes egy kis adathalmazt párhuzamosan rendezni, még akkor sem, ha nagy számú rendelkezésre álló számítási erőforrással rendelkezik, vagy az összehasonlító függvény vagy kivonatfüggvény viszonylag nagy mennyiségű munkát végez. A kis adathalmazok rendezéséhez használhatja az std::sort függvényt. (parallel_sort és parallel_buffered_sort hívja meg sort , ha az adathalmaznál nagyobb adattömbméretet ad meg; parallel_buffered_sort azonban O(N) területet kellene lefoglalnia, ami a zárolási versengés vagy a memóriafoglalás miatt további időt vehet igénybe.)

Ha spórolnia kell a memóriával, vagy a memória-kiosztó zárolási versengéssel terhelt, használjon parallel_sort közepes méretű adathalmaz rendezésére. parallel_sort nem igényel további helyet; a többi algoritmushoz O(N) térre van szükség.

Közepes méretű adathalmazok rendezésére és az alkalmazás további O(N) helyigényének teljesítése esetén használható a parallel_buffered_sort. parallel_buffered_sort különösen akkor lehet hasznos, ha nagy mennyiségű számítási erőforrással vagy költséges összehasonlító függvénnyel vagy kivonatoló függvénnyel rendelkezik.

Nagy adathalmazok rendezésére használható parallel_radixsort , és amikor az alkalmazás megfelel a további O(N) helyigénynek. parallel_radixsort különösen akkor lehet hasznos, ha az egyenértékű összehasonlítási művelet drágább, vagy ha mindkét művelet költséges.

Figyelmeztetés

Egy jó kivonatoló függvény implementálásához ismernie kell az adathalmaz tartományát, és azt, hogy az adathalmaz egyes elemei hogyan lesznek átalakítva egy megfelelő aláíratlan értékre. Mivel a kivonatolási művelet nem aláírt értékeken működik, fontolja meg egy másik rendezési stratégiát, ha nem aláírt kivonatértékek nem hozhatók létre.

Az alábbi példa összehasonlítja a sort, parallel_sort, parallel_buffered_sort és parallel_radixsort teljesítményét ugyanazon nagy mennyiségű random adat ellen.

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

Ebben a példában, amely feltételezi, hogy a rendezés során elfogadható az O(N) terület lefoglalása, parallel_radixsort a legjobb teljesítményt nyújtja ezen az adatkészleten ezen a számítógépen.

[Felső]

Kapcsolódó témakörök

Cím	Leírás
Útmutató: parallel_for ciklus írása	Bemutatja, hogyan használhatja az algoritmust mátrix-szorzás parallel_for végrehajtására.
Hogyan írjunk parallel_for_each ciklust	Bemutatja, hogyan számítható ki az parallel_for_each objektumban lévő prímszámok száma párhuzamosan az algoritmus használatával.
Útmutató: Párhuzamos rendezési rutin írása parallel_invoke használatával	Bemutatja, hogyan javíthatja a parallel_invoke bitonikus rendezési algoritmus teljesítményét az algoritmus használatával.
Útmutató: Párhuzamos műveletek végrehajtása parallel_invoke használatával	Bemutatja, hogyan javíthatja az algoritmust parallel_invoke egy olyan program teljesítményének javítására, amely több műveletet hajt végre egy megosztott adatforráson.
Útmutató: Térkép- és csökkentési műveletek végrehajtása párhuzamosan	Bemutatja, hogyan használhatja az parallel_transformparallel_reduce és az algoritmusokat egy olyan térkép és csökkentési művelet végrehajtására, amely megszámlálja a szavak előfordulását a fájlokban.
Párhuzamos minták kódtára (PPL)	Ismerteti a PPL-t, amely egy imperatív programozási modellt biztosít, amely elősegíti a skálázhatóságot és a könnyű használatot az egyidejű alkalmazások fejlesztéséhez.
Lemondás a PPL-ben	Ismerteti a lemondás szerepét a PPL-ben, hogyan lehet megszakítani a párhuzamos munkát, és hogyan állapítható meg, hogy egy tevékenységcsoport mikor lesz megszakítva.
Kivételkezelés	A kivételkezelés szerepét ismerteti az egyidejűségi futtatókörnyezetben.

Referenciák

parallel_for függvény

parallel_for_each függvény

parallel_invoke függvény

affinity_partitioner osztály

auto_partitioner osztály

simple_partitioner osztály

static_partitioner osztály

parallel_sort függvény

parallel_buffered_sort függvény

parallel_radixsort függvény