Útmutató: Párhuzamos rendezési rutin írása parallel_invoke használatával

Ez a dokumentum bemutatja, hogyan használható a parallel_invoke algoritmus a bitonikus rendezési algoritmus teljesítményének javítására. A bitonikus rendezési algoritmus rekurzív módon kisebb rendezett partíciókra osztja a bemeneti sorozatot. A bitonikus rendezési algoritmus párhuzamosan is futtatható, mert minden partícióművelet független minden más műveletétől.

Bár a bitens rendezés egy példa egy olyan rendezési hálózatra , amely a bemeneti szekvenciák összes kombinációját rendezi, ez a példa azokat a sorozatokat rendezi, amelyeknek a hossza kettő.

Megjegyzés:

Ez a példa egy párhuzamos rendezési rutint használ az ábrához. A PPL által biztosított beépített rendezési algoritmusokat is használhatja: egyidejűség::parallel_sort, egyidejűség::parallel_buffered_sort és egyidejűség::parallel_radixsort. További információ: Párhuzamos algoritmusok.

Szakaszok

Ez a dokumentum a következő feladatokat ismerteti:

Bitonikus rendezés soros végrehajtása
A parallel_invoke használata a bitonikus rendezés párhuzamos végrehajtásához

Bitonikus rendezés soros végrehajtása

Az alábbi példa a bitonikus rendezési algoritmus soros verzióját mutatja be. A bitonic_sort függvény két partícióra osztja a sorrendet, ellentétes irányba rendezi ezeket a partíciókat, majd egyesíti az eredményeket. Ez a függvény kétszer hívja meg magát rekurzívan az egyes partíciók rendezéséhez.

const bool INCREASING = true;
const bool DECREASING = false;

// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
   if (dir == (items[i] > items[j]))
   {
      swap(items[i], items[j]);
   }
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }
      bitonic_merge(items, lo, m, dir);
      bitonic_merge(items, lo + m, m, dir);
   }
}

// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;
      bitonic_sort(items, lo, m, INCREASING);
      bitonic_sort(items, lo + m, m, DECREASING);

      // Merge the results.
      bitonic_merge(items,lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
    bitonic_sort(items, 0, size, INCREASING);
}

[Felső]

A parallel_invoke használata a bitonikus rendezés párhuzamos végrehajtásához

Ez a szakasz azt ismerteti, hogyan használható az parallel_invoke algoritmus a bitonikus rendezési algoritmus párhuzamos végrehajtására.

A bitonikus rendezési algoritmus párhuzamos végrehajtása érdekében

Adjon hozzá egy #include irányelvet a ppl.h fejlécfájlhoz.
```
#include <ppl.h>
```
Adjon hozzá egy direktívát using a concurrency névtérhez.
```
using namespace concurrency;
```

Hozzon létre egy új, úgynevezett parallel_bitonic_megefüggvényt, amely az parallel_invoke algoritmus használatával egyesíti a szekvenciákat párhuzamosan, ha elegendő munka áll rendelkezésre. Ellenkező esetben hívja meg bitonic_merge, hogy sorosan egyesítse a sorozatokat.

// Sorts a bitonic sequence in the specified order.
template <class T>
void parallel_bitonic_merge(T* items, int lo, int n, bool dir)
{   
   // Merge the sequences concurrently if there is sufficient work to do.
   if (n > 500)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }

      // Use the parallel_invoke algorithm to merge the sequences in parallel.
      parallel_invoke(
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); },
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); }
      );
   }
   // Otherwise, perform the work serially.
   else if (n > 1)
   {
      bitonic_merge(items, lo, n, dir);
   }   
}

Hajtsa végre azt a folyamatot, amely hasonlít az előző lépés folyamatára, de a bitonic_sort függvényre vonatkozóan.

// Sorts the given sequence in the specified order.
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{   
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

Hozza létre a parallel_bitonic_sort függvény túlterhelt verzióját, amely növekvő sorrendben rendezi a tömböt.
```
// Sorts the given sequence in increasing order.
template <class T>
void parallel_bitonic_sort(T* items, int size)
{
   parallel_bitonic_sort(items, 0, size, INCREASING);
}
```
Az parallel_invoke algoritmus csökkenti a többletterhelést azáltal, hogy a hívókörnyezetben az utolsó feladatsort hajtja végre. A függvényben például az parallel_bitonic_sort első tevékenység egy külön környezetben fut, a második pedig a hívókörnyezetben.
```
// Sort the partitions in parallel.
parallel_invoke(
   [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
   [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
);
```

Az alábbi teljes példa a bitonikus rendezési algoritmus soros és párhuzamos verzióit is végrehajtja. A példa az egyes számítások elvégzéséhez szükséges időt is kinyomtatja a konzolon.

// parallel-bitonic-sort.cpp
// compile with: /EHsc
#include <windows.h>
#include <algorithm>
#include <iostream>
#include <random>
#include <ppl.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 bool INCREASING = true;
const bool DECREASING = false;

// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
   if (dir == (items[i] > items[j]))
   {
      swap(items[i], items[j]);
   }
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }
      bitonic_merge(items, lo, m, dir);
      bitonic_merge(items, lo + m, m, dir);
   }
}

// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;
      bitonic_sort(items, lo, m, INCREASING);
      bitonic_sort(items, lo + m, m, DECREASING);

      // Merge the results.
      bitonic_merge(items,lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
    bitonic_sort(items, 0, size, INCREASING);
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void parallel_bitonic_merge(T* items, int lo, int n, bool dir)
{   
   // Merge the sequences concurrently if there is sufficient work to do.
   if (n > 500)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }

      // Use the parallel_invoke algorithm to merge the sequences in parallel.
      parallel_invoke(
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); },
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); }
      );
   }
   // Otherwise, perform the work serially.
   else if (n > 1)
   {
      bitonic_merge(items, lo, n, dir);
   }   
}

// Sorts the given sequence in the specified order.
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{   
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void parallel_bitonic_sort(T* items, int size)
{
   parallel_bitonic_sort(items, 0, size, INCREASING);
}

int wmain()
{  
   // For this example, the size must be a power of two.
   const int size = 0x200000;

   // Create two large arrays and fill them with random values.
   int* a1 = new int[size];
   int* a2 = new int[size];

   mt19937 gen(42);
   for(int i = 0; i < size; ++i)
   {
      a1[i] = a2[i] = gen();
   }

   __int64 elapsed;
   
   // Perform the serial version of the sort.
   elapsed = time_call([&] { bitonic_sort(a1, size); });
   wcout << L"serial time: " << elapsed << endl;

   // Now perform the parallel version of the sort.
   elapsed = time_call([&] { parallel_bitonic_sort(a2, size); });
   wcout << L"parallel time: " << elapsed << endl;
 
   delete[] a1;
   delete[] a2;
}

Az alábbi mintakimenet egy négy processzorral rendelkező számítógéphez készült.

serial time: 4353
parallel time: 1248

[Felső]

A kód összeállítása

A kód fordításához másolja ki, majd illessze be egy Visual Studio-projektbe, vagy illessze be egy elnevezett parallel-bitonic-sort.cpp fájlba, majd futtassa a következő parancsot egy Visual Studio parancssori ablakban.

cl.exe /EHsc parallel-bitonic-sort.cpp

Robusztus programozás

Ez a példa a parallel_invoke algoritmust használja a concurrency::task_group osztály helyett, mert az egyes tevékenységcsoportok élettartama nem terjed túl egy függvényen. Azt javasoljuk, hogy akkor használja parallel_invoke , ha lehetséges, mert kevesebb végrehajtási többletterheléssel rendelkezik, mint task group az objektumok, ezért lehetővé teszi a kód jobb írását.

Egyes algoritmusok párhuzamos verziói csak akkor működnek jobban, ha elegendő munka áll rendelkezésre. A függvény meghívja például parallel_bitonic_merge a soros verziót, bitonic_mergeha a sorozatnak 500 vagy kevesebb eleme van. Az általános rendezési stratégiát a munkamennyiség alapján is megtervezheti. Például hatékonyabb lehet a gyors rendezési algoritmus soros verziójának használata, ha a tömb 500-nál kevesebb elemet tartalmaz, ahogyan az alábbi példában látható:

template <class T>
void quick_sort(T* items, int lo, int n)
{
   // TODO: The function body is omitted for brevity.
}

template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{
   // Use the serial quick sort algorithm if there are relatively few
   // items to sort. The associated overhead for running few tasks in 
   // parallel may not overcome the benefits of parallel processing.
   if (n - lo + 1 <= 500)
   {
      quick_sort(items, lo, n);
   }
   else if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

A párhuzamos algoritmusokhoz hasonlóan javasoljuk, hogy a kódot a megfelelő módon profilozza és hangolja.

Lásd még

Feladat-párhuzamosság
parallel_invoke függvény

Visszajelzés

Hasznosnak találta ezt az oldalt?

Last updated on 2025-11-07