Практическое руководство. Использование функции parallel_invoke для написания программы параллельной сортировки

Статья
08/11/2011

В этом документе описано, как использовать алгоритм parallel_invoke для повышения производительности алгоритма битонной сортировки. Алгоритм битонной сортировки рекурсивно разделяет входную последовательность на сортированные разделы меньшего размера. Алгоритм битонной сортировки может выполняться параллельно, потому что каждая операция разделения независима от всех других операций.

Несмотря на то что битонная сортировка является примером сети сортировки, которая сортирует все сочетания входных последовательностей, в этом примере выполняется сортировка последовательностей, длина которых представляет собой степень числа два.

Подразделы

В этом документе описаны следующие задачи.

Последовательное выполнение битонной сортировки
Использование parallel_invoke для параллельного выполнения битонной сортировки

Последовательное выполнение битонной сортировки

В следующем примере показана последовательная реализация алгоритма битонной сортировки. Функция bitonic_sort разделяет последовательность на два раздела, сортирует эти разделы в противоположных направлениях и объединяет результаты. Эта функция рекурсивно вызывает себя дважды, чтобы отсортировать каждый раздел.

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

[в начало]

Использование parallel_invoke для параллельного выполнения битонной сортировки

В этом разделе описано, как использовать алгоритм parallel_invoke для параллельного выполнения алгоритма битонной сортировки.

Процедуры

Параллельное выполнение алгоритма битонной сортировки

Добавьте директиву #include для файла заголовка ppl.h.
```
#include <ppl.h>
```
Добавьте директиву using для пространства имен Concurrency.
```
using namespace Concurrency;
```

Создайте новую функцию с именем parallel_bitonic_mege, которая использует алгоритм parallel_invoke, чтобы объединить последовательности параллельно, если выполняемой работы достаточно. В противном случае вызовите bitonic_merge, чтобы объединить последовательности последовательно.

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

Выполните для функции 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);
   }
}

Создайте перегруженную версию функции parallel_bitonic_sort, сортирующую массив по возрастанию.

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

Алгоритм parallel_invoke снижает нагрузку на систему, выполняя последний ряд задач в вызывающем контексте. Например, в функции parallel_bitonic_sort первая задача выполняется в отдельном контексте, а вторая — в контексте вызова.

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

В следующем полном примере показаны последовательная и параллельная реализации алгоритма битонной сортировки. В этом примере на консоль также выводится продолжительность выполнения каждого вычисления.

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

В следующем примере показаны выходные данные, полученные на четырехпроцессорном компьютере.

serial time: 4353
parallel time: 1248

[в начало]

Компиляция кода

Чтобы скомпилировать код, скопируйте и вставьте его в проект Visual Studio или в файл с именем parallel-bitonic-sort.cpp, затем выполните в окне командной строки Visual Studio следующую команду.

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

Надежное программирование

В этом примере алгоритм parallel_invoke используется вместо класса Concurrency::task_group, потому что время существования каждой группы задач не выходит за пределы функции. Рекомендуется по возможности использовать алгоритм parallel_invoke, так как при его выполнении нагрузка на систему меньше, чем при выполнении объектов task group, что позволяет писать более производительный код.

Параллельные версии некоторых алгоритмов функционируют более эффективно, если имеется достаточный объем работы. Например, функция parallel_bitonic_merge вызывает последовательную версию, bitonic_merge, если в последовательности 500 элементов или меньше. Также можно планировать общую стратегию сортировки на основании объемов работы. Например, использование последовательной версии алгоритма быстрой сортировки может быть эффективнее, если массив содержит менее 500 элементов, как показано в следующем примере.

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

Как и с другими параллельными алгоритмами, рекомендуется соответствующим образом профилировать и оптимизировать код.

См. также

Ссылки

Функция parallel_invoke

Основные понятия

Параллелизм задач (среда выполнения с параллелизмом)

Журнал изменений

Дата	Журнал	Причина
Июль 2010	Пример обновлен и использует parallel_invoke.	Улучшение информации.

Июль 2010

Пример обновлен и использует parallel_invoke.

Улучшение информации.

Share via