Delen via

Hoe gebruik je parallel_invoke om een parallelle sorteerroutine te schrijven?

In dit document wordt beschreven hoe u het parallel_invoke-algoritme gebruikt om de prestaties van het bitonische sorteeralgoritmen te verbeteren. Het bitonische sorteeralgoritmen verdelen de invoerreeks recursief in kleinere gesorteerde partities. Het bitonic-sorteeralgoritmen kunnen parallel worden uitgevoerd omdat elke partitiebewerking onafhankelijk is van alle andere bewerkingen.

Hoewel de bitonische sortering een voorbeeld is van een sorteernetwerk dat alle combinaties van invoerreeksen sorteert, worden in dit voorbeeld reeksen gesorteerd waarvan de lengte een macht van twee is.

Opmerking

In dit voorbeeld wordt een parallelle sorteerroutine gebruikt voor illustratie. U kunt ook de ingebouwde sorteeralgoritmen gebruiken die de PPL biedt: concurrency::parallel_sort, concurrency::parallel_buffered_sort en concurrency::parallel_radixsort. Zie Parallelle algoritmenvoor meer informatie.

Afdelingen

In dit document worden de volgende taken beschreven:

Bitonic sorteren serieel uitvoeren

In het volgende voorbeeld ziet u de seriële versie van het bitonische sorteeralgoritmen. De bitonic_sort functie verdeelt de reeks in twee partities, sorteert deze partities in tegenovergestelde richtingen en voegt vervolgens de resultaten samen. Deze functie roept zichzelf twee keer recursief aan om elke partitie te sorteren.

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

[Boven]

Bitonische sortering parallel uitvoeren met parallel_invoke

In deze sectie wordt beschreven hoe u het parallel_invoke algoritme gebruikt om het bitonische sorteeralgoritmen parallel uit te voeren.

Het bitonische sorteeralgoritme parallel uitvoeren

  1. Voeg een #include instructie toe voor het headerbestand ppl.h.

    #include <ppl.h>

  2. Voeg een using instructie toe voor de concurrency naamruimte.

    using namespace concurrency;

  3. Maak een nieuwe functie, aangeroepen parallel_bitonic_mege, die het parallel_invoke algoritme gebruikt om de reeksen parallel samen te voegen als er voldoende werk te doen is. Anders roept u bitonic_merge aan om de reeksen serieel samen te voegen.

    // 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. Voer een proces uit dat lijkt op het proces in de vorige stap, maar dan voor de functie bitonic_sort.

    // 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. Maak een overbelaste versie van de parallel_bitonic_sort functie waarmee de matrix in oplopende volgorde wordt gesorteerd.

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

    Het parallel_invoke algoritme vermindert de overhead door de laatste van de reeks taken in de aanroepende context uit te voeren. In de parallel_bitonic_sort functie wordt de eerste taak bijvoorbeeld uitgevoerd in een afzonderlijke context en wordt de tweede taak uitgevoerd in de aanroepende context.

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

In het volgende volledige voorbeeld worden zowel de seriële als de parallelle versies van het bitonische sorteeralgoritmen uitgevoerd. In het voorbeeld wordt ook op de console de tijd weergegeven die nodig is om elke berekening uit te voeren.

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

De volgende voorbeelduitvoer is voor een computer met vier processors.

serial time: 4353
parallel time: 1248

[Boven]

De code compileren

Als u de code wilt compileren, kopieert u deze en plakt u deze in een Visual Studio-project of plakt u deze in een bestand met de naam parallel-bitonic-sort.cpp en voert u vervolgens de volgende opdracht uit in een Visual Studio-opdrachtpromptvenster.

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

Robuuste programmering

In dit voorbeeld wordt het parallel_invoke algoritme gebruikt in plaats van de gelijktijdigheid::task_group klasse omdat de levensduur van elke taakgroep niet verder gaat dan een functie. U wordt aangeraden parallel_invoke te gebruiken wanneer u dat kunt, omdat deze minder overhead voor de uitvoering heeft dan task group-objecten, waardoor u beter presterende code kunt schrijven.

De parallelle versies van sommige algoritmen presteren alleen beter wanneer er voldoende werk te doen is. De functie roept bijvoorbeeld parallel_bitonic_merge de seriële versie aan, bitonic_mergeals er 500 of minder elementen in de reeks staan. U kunt ook uw algehele sorteerstrategie plannen op basis van de hoeveelheid werk. Het kan bijvoorbeeld efficiënter zijn om de seriële versie van het algoritme voor snelle sortering te gebruiken als de matrix minder dan 500 items bevat, zoals wordt weergegeven in het volgende voorbeeld:

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

Net als bij elk parallel algoritme raden we u aan uw code zo nodig te profilen en af te stemmen.

Zie ook

Parallelle uitvoering van taken
parallel_invoke, functie

  • Last updated on