Gewusst wie: Verwenden von parallel_invoke zum Schreiben einer Runtime für paralleles Sortieren

In diesem Dokument wird beschrieben, wie mit dem parallel_invoke-Algorithmus die Leistung des bitonischen Sortieralgorithmus verbessert werden kann. Der bitonische Sortieralgorithmus unterteilt die Eingabesequenz rekursiv in kleinere sortierte Partitionen. Der bitonische Sortieralgorithmus kann parallel ausgeführt werden, da alle Partitionsvorgänge von allen anderen Vorgängen unabhängig sind.

Obwohl das bitonische Sortieren ein Beispiel für ein Sortiernetzwerk ist, das alle Kombinationen von Eingabesequenzen sortiert, werden in diesem Beispiel Sequenzen sortiert, deren Länge eine Potenz von zwei ist.

Abschnitte

In diesem Dokument werden die folgenden Aufgaben erläutert:

• Serielles Ausführen der bitonischen Sortierung

• Verwenden von parallel_invoke für die parallele bitonische Suche

Serielles Ausführen der bitonischen Sortierung

Im folgenden Beispiel wird die serielle Version des bitonischen Sortieralgorithmus dargestellt. Die bitonic_sort-Funktion unterteilt die Sequenz in zwei Partitionen, sortiert diese Partitionen in entgegengesetzten Richtungen, und führt dann die Ergebnisse zusammen. Diese Funktion ruft sich selbst zweimal auf, um alle Partitionen rekursiv zu sortieren.

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

[Nach oben]

Verwenden von parallel_invoke für die parallele bitonische Suche

In diesem Abschnitt wird beschrieben, wie der bitonischen Sortieralgorithmus mit dem parallel_invoke-Algorithmus parallel ausgeführt werden kann.

Prozeduren

So führen Sie den bitonischen Sortieralgorithmus parallel aus

1. Fügen Sie für die Headerdatei ppl.h eine #include-Direktive hinzu.

   #include <ppl.h>
   

2. Fügen Sie für den Concurrency-Namespace eine using-Direktive hinzu.

   using namespace Concurrency;
   

3. Erstellen Sie die neue Funktion parallel_bitonic_mege für den parallel_invoke-Algorithmus, um die Sequenzen parallel zusammenzuführen, wenn genügend Arbeit vorhanden ist. Rufen Sie andernfalls bitonic_merge auf, um die Sequenzen seriell zusammenzuführen.

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

4. Führen Sie einen Prozess aus, der demjenigen im Schritt weiter oben gleicht, jedoch für die bitonic_sort-Funktion ausgeführt wird.

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

5. Erstellen Sie eine überladene Version der parallel_bitonic_sort-Funktion, durch die das Array in aufsteigender Reihenfolge sortiert wird.

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

Mit dem parallel_invoke-Algorithmus wird der Aufwand reduziert, indem die letzte einer Reihe von Aufgaben im aufrufenden Kontext ausgeführt wird. Beispielsweise wird in der parallel_bitonic_sort-Funktion die erste Aufgabe in einem separaten Kontext und die zweite Aufgabe im aufrufenden Kontext ausgeführt.

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

Im folgenden vollständigen Beispiel wird sowohl die serielle als auch die parallele Version des bitonischen Sortieralgorithmus durchgeführt. Das Beispiel gibt außerdem die Zeit, die zum Ausführen beider Berechnungen benötigt wird, an der Konsole aus.

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

Die folgende Beispielausgabe entspricht einem Ergebnis auf einem Computer mit vier Prozessoren.

serial time: 4353
parallel time: 1248

[Nach oben]

Kompilieren des Codes

Kopieren Sie den Code zum Kompilieren in ein Visual Studio-Projekt, oder fügen Sie ihn in eine Datei mit dem Namen parallel-bitonic-sort.cpp ein, und führen Sie dann den folgenden Befehl in einem Visual Studio-Eingabeaufforderungsfenster aus.

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

Stabile Programmierung

In diesem Beispiel wird anstelle der Concurrency::task_group-Klasse der parallel_invoke-Algorithums verwendet, da die Lebensdauer der einzelnen Aufgabengruppen nicht über eine Funktion hinausreicht. Es wird empfohlen, wenn möglich parallel_invoke-Objekte zu verwenden, da diese im Vergleich zu task group-Objekten einen geringeren Ausführungsaufwand erfordern, sodass Sie einen leistungsfähigeren Code schreiben können.

Die parallelen Versionen einiger Algorithmen erzielen nur eine bessere Leistung, wenn es genügend Arbeit gibt. So ruft beispielsweise die parallel_bitonic_merge-Funktion die serielle Version bitonic_merge auf, wenn in der Sequenz 500 oder weniger Elemente vorhanden sind. Sie können die allgemeine Vorgehensweise bei der Sortierung auch an dem voraussichtlichen Arbeitsaufwand ausrichten. Beispielsweise ist es möglicherweise effizienter, die serielle Version des QuickSort-Algorithmus zu verwenden, wenn das Array weniger als 500 Elemente enthält, wie im folgenden Beispiel gezeigt:

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

Analog zu allen anderen parallelen Algorithmen wird empfohlen, nach Bedarf Profile und Anpassungen für den Code bereitzustellen.

Siehe auch

Referenz

parallel_invoke-Funktion

Konzepte

Aufgabenparallelität (Concurrency Runtime)

Änderungsprotokoll