Параллельные алгоритмы

Библиотека параллельных шаблонов (PPL) предоставляет алгоритмы, которые параллельно выполняют работу над коллекциями данных. Эти алгоритмы похожи на те, которые предоставляются стандартной библиотекой C++.

Параллельные алгоритмы состоят из существующих функций в среде выполнения параллелизма. Например, параллелизм::p arallel_for algorithm использует объект параллелизма::structured_task_group для выполнения итерации параллельного цикла. parallel_for Секции алгоритмов работают оптимально, учитывая доступное количество вычислительных ресурсов.

Разделы

• Алгоритм parallel_for

• Алгоритм parallel_for_each

• Алгоритм parallel_invoke

• Алгоритмы parallel_transform и parallel_reduce

  • Алгоритм parallel_transform

  • Алгоритм parallel_reduce

  • Пример. Выполнение сопоставления и уменьшения числа параллельных операций

• Работа с секционированием

• Параллельная сортировка

  • Выбор алгоритма сортировки

Алгоритм parallel_for

Параллелизм ::p arallel_for алгоритм многократно выполняет одну и ту же задачу параллельно. Каждая из этих задач параметризуется значением итерации. Этот алгоритм полезен, если у вас есть текст цикла, который не использует ресурсы между итерациями этого цикла.

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

У алгоритма parallel_for существует несколько перегруженных версий. Первая версия принимает начальное значение, конечное значение и рабочую функцию (лямбда-выражение, объект функции или указатель функции). Вторая версия принимает начальное значение, конечное значение, значение, по которому выполняется шаг, и рабочая функция. Первая версия этой функции использует 1 в качестве значения шага. Остальные версии принимают объекты-разделители, позволяющие указать, как алгоритм parallel_for должен разделять диапазоны между потоками. Секционаторы подробно описаны в разделе Секционирование работы в этом документе.

Для использования parallel_forможно преобразовать множество for циклов. parallel_for Однако алгоритм отличается от инструкции for следующими способами:

• Алгоритм parallel_for parallel_for не выполняет задачи в предопределенном порядке.

• Алгоритм parallel_for не поддерживает произвольные условия завершения. Алгоритм parallel_for останавливается, если текущее значение переменной итерации меньше last.

• Параметр _Index_type типа должен быть целочисленным типом. Этот целочисленный тип можно подписать или отменить подпись.

• Итерация цикла должна быть переадресации. Алгоритм parallel_for создает исключение типа std::invalid_argument , если _Step параметр меньше 1.

• Механизм обработки исключений для parallel_for алгоритма отличается от механизма обработки исключений for . Если несколько исключений происходят одновременно в теле параллельного цикла, среда выполнения распространяет только одно из исключений в вызываемом parallel_forпотоке. Кроме того, если одно итерация цикла вызывает исключение, среда выполнения не сразу останавливает общий цикл. Вместо этого цикл помещается в отмененное состояние, а среда выполнения удаляет все задачи, которые еще не начались. Дополнительные сведения об обработке исключений и параллельных алгоритмах см. в разделе "Обработка исключений".

parallel_for Хотя алгоритм не поддерживает произвольные условия завершения, можно использовать отмену для остановки всех задач. Дополнительные сведения об отмене см. в разделе "Отмена" в PPL.

Примечание.

Стоимость планирования, которая приводит к балансировке нагрузки и поддержке таких функций, как отмена, может не преодолеть преимущества параллельного выполнения текста цикла, особенно если тело цикла относительно небольшое. Эту дополнительную нагрузку можно минимизировать, используя разделитель в параллельном цикле. Дополнительные сведения см. в разделе "Работа секционирования" далее в этом документе.

Пример

В следующем примере показана базовая структура алгоритма parallel_for . В этом примере выполняется печать на консоль каждого значения в диапазоне [1, 5] параллельно.

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

В этом примере создаются следующие примеры выходных данных:

1 2 4 3 5

parallel_for Так как алгоритм действует на каждом элементе параллельно, порядок печати значений в консоли будет отличаться.

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

[В начало]

Алгоритм parallel_for_each

Алгоритм параллелизма::p arallel_for_each выполняет задачи в итеративном контейнере, например в стандартной библиотеке C++ параллельно. Он использует ту же логику секционирования, что parallel_for и алгоритм.

Алгоритм parallel_for_each напоминает алгоритм стандартной библиотеки C++ std::for_each , за исключением того, что parallel_for_each алгоритм выполняет задачи одновременно. Как и другие параллельные алгоритмы, parallel_for_each не выполняют задачи в определенном порядке.

parallel_for_each Хотя алгоритм работает как на итераторах пересылки, так и на случайных итераторах доступа, он лучше работает с итераторами случайного доступа.

Пример

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

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

В этом примере создаются следующие примеры выходных данных:

4 5 1 2 3

parallel_for_each Так как алгоритм действует на каждом элементе параллельно, порядок печати значений в консоли будет отличаться.

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

[В начало]

Алгоритм parallel_invoke

Алгоритм параллелизма::p arallel_invoke выполняет набор задач параллельно. Он не возвращается до завершения каждой задачи. Этот алгоритм полезен при наличии нескольких независимых задач, которые необходимо выполнять одновременно.

Алгоритм parallel_invoke принимает в качестве параметров ряд рабочих функций (лямбда-функции, объекты функций или указатели функций). Алгоритм parallel_invoke перегружается для принятия между двумя и десятью параметрами. Каждая передаваемая parallel_invoke функция должна принимать нулевые параметры.

Как и другие параллельные алгоритмы, parallel_invoke не выполняют задачи в определенном порядке. В разделе " Параллелизм задач" объясняется, как parallel_invoke алгоритм связан с задачами и группами задач.

Пример

В следующем примере показана базовая структура алгоритма parallel_invoke . Этот пример параллельно вызывает функцию twice для трех локальных переменных и выводит результат в консоль.

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

В примере получается следующий вывод.

108 11.2 HelloHello

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

[В начало]

Алгоритмы parallel_transform и parallel_reduce

Алгоритмы параллелизма::p arallel_transform и concurrency::p arallel_reduce являются параллельными версиями алгоритмов стандартной библиотеки C++ std::transform и std::accumulate соответственно. Версии среды выполнения параллелизма работают так, как версии стандартной библиотеки C++, за исключением того, что порядок операции не определен, так как они выполняются параллельно. Используйте эти алгоритмы при работе с набором, который достаточно велик для получения выигрыша в производительности и масштабируемости при параллельной обработке.

Внимание

Алгоритмы parallel_transform и parallel_reduce поддерживают только итераторы произвольного доступа, двунаправленные и прямые итераторы, поскольку эти итераторы создают стабильные адреса памяти. Кроме того, эти итераторы должны создавать l-значения, отличные от const.

Алгоритм parallel_transform

Алгоритм parallel transform можно использовать для выполнения множества операций параллелизации данных. Например, доступны следующие возможности:

• Настройка яркости изображения и другие операции обработки изображений.

• Суммирование или получение скалярного произведения двух векторов и выполнение других векторных вычислений.

• Трассировка трехмерных лучей, при которой каждая итерация относится к одному пикселю, подлежащему отображению.

В следующем примере показана базовая структура, используемая для вызова алгоритма parallel_transform. Этот пример отрицает каждый элемент объекта std::vector двумя способами. В первом способе используется лямбда-выражение. Второй способ использует std::negate, производный от std::unary_function.

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

Предупреждение

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

Алгоритм parallel_transform имеет две перегрузки. Первая перегрузка принимает один входной диапазон и унарную функцию. Унарная функция может быть лямбда-выражением, принимающим один аргумент, объект функции или тип, производный от unary_function. Вторая перегрузка принимает два входных диапазона и бинарную функцию. Двоичная функция может быть лямбда-выражением, которое принимает два аргумента, объект функции или тип, производный от std::binary_function. В следующем примере показаны эти различия.

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

Внимание

Итератор, предоставляемый для выходных данных алгоритма parallel_transform, должен полностью перекрывать итератор входных данных или не перекрывать его вообще. Если итераторы входных и выходных данных перекрываются частично, поведение этого алгоритма будет неопределенным.

Алгоритм parallel_reduce

Алгоритм parallel_reduce эффективен при наличии последовательности операций, обладающих свойством ассоциативности. (Этот алгоритм не требует коммутативного свойства.) Ниже приведены некоторые операции, которые можно выполнить с помощью parallel_reduce:

• умножение последовательности матриц для получения матрицы;

• умножение вектора на последовательность матриц для получения вектора;

• вычисление длины последовательности строк;

• объединение списка элементов, например строк, в один элемент.

В следующем базовом примере показано использование алгоритма parallel_reduce для объединения последовательности строк в одну строку. Как и в примерах для parallel_transform, в этом базовом примере не ожидается повышения производительности.

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

Во многих случаях можно рассматривать parallel_reduce как сокращенное использование алгоритма parallel_for_each вместе с классом concurrency::combinable .

Пример. Выполнение сопоставления и уменьшения числа параллельных операций

Операция сопоставления применяет функцию к каждому значению последовательности. Операция уменьшения объединяет элементы последовательности в одно значение. Вы можете использовать стандартную библиотеку C++ std::transform и std::аккумулировать функции для выполнения операций сопоставления и уменьшения. Однако для многих задач можно использовать алгоритм parallel_transform для параллельного выполнения операции сопоставления и алгоритм parallel_reduce для параллельного выполнения операции редукции.

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

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

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

[В начало]

Работа с секционированием

Чтобы параллелизировать операцию в источнике данных, необходимо разделить источник на несколько разделов, к которым можно получить доступ одновременно с несколькими потоками. Разделитель определяет, как параллельный алгоритм должен разделять диапазоны между потоками. Как описано ранее в этом документе, PPL использует механизм секционирования по умолчанию, создающий начальную рабочую нагрузку, а затем применяет алгоритм переноса нагрузки и переноса диапазона для распределения нагрузки этих разделов при ее несбалансированности. Например, когда одна итерация цикла завершает ряд итераций, среда выполнения перераспределяет в этот поток нагрузку с других потоков. Однако в некоторых сценариях может потребоваться указать другой механизм секционирования, который лучше подходит для конкретной задачи.

Алгоритмы parallel_for, parallel_for_each и parallel_transform предоставляют перегруженные версии, принимающие дополнительный параметр _Partitioner. Этот параметр определяет тип разделителя, разделяющий работу. Ниже указаны типы разделителей, которые определяет PPL.

concurrency::affinity_partitioner
Разделяет нагрузку на фиксированное число диапазонов (обычно число рабочих потоков, доступных для работы в цикле). Этот тип разделителя напоминает static_partitioner, но повышает степень сходства кэша путем сопоставления диапазонов рабочим потокам. Такой тип разделителя может повысить производительность, если цикл выполняется над одним и тем же набором данных несколько раз (например, цикл в цикле) и данные размещаются в кэше. Этот разделитель не полностью участвует в отмене. Он также не использует согласованную семантику блокировки и поэтому не может использоваться с параллельными циклами, имеющими прямую зависимость.

параллелизм::auto_partitioner
Разделяет нагрузку на начальное число диапазонов (обычно число рабочих потоков, доступных для работы в цикле). Среда выполнения использует этот тип по умолчанию, если не вызывается перегруженный параллельный алгоритм, принимающий параметр _Partitioner. Каждый диапазон можно разделить на поддиапазоны, что обеспечивает распределение нагрузки. Когда диапазон работы завершается, среда выполнения перераспределяет поддиапазоны работы с других потоков в этот поток. Используйте этот разделитель, если рабочая нагрузка не попадает в другие категории или требуется полная поддержка отмены или совместной блокировки.

параллелизм::simple_partitioner
Разделяет нагрузку на диапазоны так, чтобы каждый диапазон содержал по крайней мере такое число итераций, которое определено заданным размером блока. Этот тип разделителя участвует в распределении нагрузки; однако среда выполнения не делит диапазоны на поддиапазоны. Для каждого рабочего потока среда выполнения проверяет запрос отмены и выполняет распределение нагрузки после завершения числа итераций, определенных параметром _Chunk_size.

параллелизм::static_partitioner
Разделяет нагрузку на фиксированное число диапазонов (обычно число рабочих потоков, доступных для работы в цикле). Этот разделитель может повысить производительность, поскольку не использует перенос нагрузки и, следовательно, содержит меньше побочной нагрузки. Используйте его, если при каждой итерации параллельного цикла выполняется фиксированный и одинаковый объем работы и нет необходимости поддержки отмены или прямой совместной блокировки.

Предупреждение

Алгоритмы parallel_for_each поддерживают только контейнеры, использующие итераторы случайного доступа (например, std::vector) для статических, простых и сходства секционаторов.parallel_transform Применение контейнеров, использующих двунаправленные и прямые итераторы, приводит к ошибке во время компиляции. Разделитель по умолчанию auto_partitioner поддерживает все три типа итераторов.

Обычно эти разделители используются одинаково, за исключением affinity_partitioner. Большинство типов разделителей не поддерживают состояние и не изменяются средой выполнения. Поэтому эти объекты-разделители можно создавать в месте вызова, как показано в следующем примере.

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

Однако необходимо передать объект affinity_partitioner как ссылку на I-значение, отличное от const, чтобы алгоритм мог сохранять состояние для повторного использования в последующих циклах. В следующем примере демонстрируется базовое приложение, параллельно выполняющее одну и ту же операцию над набором данных несколько раз. Использование affinity_partitioner позволяет повысить производительность, поскольку массив может размещаться в кэше.

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

Внимание

При изменении существующего кода, зависящего от семантики совместной блокировки при применении разделителей static_partitioner или affinity_partitioner, используйте с осторожностью. Эти разделители не используют распределение нагрузки и перенос диапазона и поэтому могут изменить поведение приложения.

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

[В начало]

Параллельная сортировка

PPL предоставляет три алгоритма сортировки: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort и concurrency::p arallel_radixsort. Они эффективны при наличии набора данных, который выгоднее сортировать параллельно. В частности, параллельная сортировка эффективна при наличии большого набора данных и использовании операций сравнения, потребляющих много вычислительных ресурсов. Каждый из этих алгоритмов сортирует элементы на месте.

Алгоритмы parallel_sort и parallel_buffered_sort основаны на сравнениях. То есть они сравнивают элементы по значению. Алгоритм parallel_sort не требует дополнительной памяти и подходит для сортировки в общем случае. Алгоритм parallel_buffered_sort может выполняться лучше, чем parallel_sortтребуется пространство O(N).

Алгоритм parallel_radixsort основан на хэше. То есть для сортировки элементов он использует целочисленные ключи. С помощью ключей этот алгоритм может определить место элемента непосредственно, а не использовать операции сравнения. Например parallel_buffered_sort, для этого алгоритма требуется пространство O(N).

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

Алгоритм	Description	Механизм сортировки	Стабильность сортировки	Требования к памяти	Временная сложность	Доступ итераторов
parallel_sort	Основанная на сравнениях сортировка общего назначения.	На основе сравнений (по возрастанию)	Работает неустойчиво	нет	O(N/P)log(N/P) + 2N(P-1)/P))	Случайные
parallel_buffered_sort	Более быстрая сортировка общего назначения на основе сравнений, для которой требуется память O(N).	На основе сравнений (по возрастанию)	Работает неустойчиво	Требуется дополнительное пространство O(N)	O(N/P)log(N)log(N))	Случайные
parallel_radixsort	Сортировка на основе целочисленных ключей, для которой требуется память О(N).	На основе хэша	Стабильный	Требуется дополнительное пространство O(N)	O(N/P)	Случайные

На следующем рисунке графически показаны важные свойства трех параллельных алгоритмов сортировки.

Эти параллельные алгоритмы сортировки подчиняются правилам отмены и обработки исключений. Дополнительные сведения об отмене и обработке исключений в среде выполнения параллелизма см. в разделе "Отмена параллельных алгоритмов" и "Обработка исключений".

Совет

Эти параллельные алгоритмы сортировки поддерживают семантику перемещений. Для более эффективного выполнения операций замены можно определить оператор присваивания перемещения. Дополнительные сведения о семантике перемещения и операторе назначения перемещения см. в статье Rvalue Reference Declarator: && и Move Конструкторы и Операторы назначения перемещения (C++). Если оператор присваивания перемещения или функция замены не предоставляется, алгоритмы сортировки используют конструктор копии.

В следующем базовом примере показано использование алгоритма parallel_sort для сортировки вектора vector значений типа int. По умолчанию parallel_sort использует std::less для сравнения значений.

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

В следующем примере показано, как реализовать пользовательскую функцию сравнения. Он использует метод std::complex::real для сортировки std::сложные<двойные> значения в порядке возрастания.

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

В следующем примере показано, как реализовать хэш-функцию для алгоритма parallel_radixsort. В этом примере сортируются трехмерные точки. Они сортируются по расстоянию от опорной точки.

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

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

В этом примере лямбда-выражение используется в качестве хэш-функции. Вы также можете использовать одну из встроенных реализаций класса std::hash или определить собственную специализацию. Кроме того, можно использовать пользовательский объект хэш-функции, как показано в следующем примере:

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

Хэш-функция должна возвращать целочисленный тип (std::is_integral::value).true Этот целочисленный тип должен быть преобразуем в тип size_t.

Выбор алгоритма сортировки

Во многих случаях алгоритм parallel_sort обеспечивает оптимальный баланс производительности памяти и быстродействия. Однако с увеличением размера набора данных, количества доступных процессоров и сложности функции сравнения алгоритм parallel_buffered_sort или parallel_radixsort может работать эффективнее. Лучший способ определения наиболее подходящего алгоритма сортировки в любом заданном сценарии — проведение экспериментов и измерение длительности выполнения сортировки типовых данных при типичных конфигурациях компьютера. Ниже приведены рекомендации по выбору стратегии сортировки.

• Размер набора данных. В этом документе небольшой набор данных содержит менее 1000 элементов, средний набор данных содержит от 10 000 до 100 000 элементов, а большой набор данных содержит более 100 000 элементов.

• Объем работы, выполняемой функцией сравнения или хэш-функцией.

• Количество доступных вычислительных ресурсов.

• Характеристики набора данных. Например, один алгоритм может хорошо работать при частично отсортированных данных, но не так хорошо, когда данные совсем не сортированы.

• Размер блока. Необязательный аргумент _Chunk_size определяет, когда алгоритм переходит от параллельной к последовательной реализации сортировки по мере разделения всей задачи сортировки на меньшие единицы работы. Например, если указать 512, то алгоритм будет переходить на последовательную реализацию, когда единица работы содержит 512 или менее элементов. При последовательной реализации может повыситься общая производительность, поскольку исключается лишняя работа, необходимая для параллельной обработки данных.

Использовать параллельную сортировку небольшого набора данных может оказаться невыгодно даже при наличии большого количества вычислительных ресурсов или выполнении функцией сравнения или хэш-функцией относительно большого объема работы. Функцию std::sort можно использовать для сортировки небольших наборов данных. (parallel_sort и parallel_buffered_sort вызов sort при указании размера блока, превышающего набор данных, однако parallel_buffered_sort потребуется выделить пространство O(N), которое может занять дополнительное время из-за блокировки конфликтов или выделения памяти.)

Если необходимо сэкономить ресурсы памяти или распределитель памяти подвержен конфликтам при блокировках, то для сортировки набора данных среднего размера следует использовать алгоритм parallel_sort. parallel_sort не требует дополнительного места; для других алгоритмов требуется пространство O(N).

Используется parallel_buffered_sort для сортировки наборов данных среднего размера и при выполнении приложения дополнительных требований к пространству O(N). Алгоритм parallel_buffered_sort особенно эффективен при большом количестве вычислительных ресурсов и ресурсоемкой функции сравнения или хэш-функции.

Используется parallel_radixsort для сортировки больших наборов данных и при выполнении приложения дополнительных требований к пространству O(N). Алгоритм parallel_radixsort особенно эффективен при ресурсоемкой функции сравнения, а также в случае, если и функция сравнения, и хэш-функция ресурсоемки.

Внимание

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

В следующем примере сравнивается производительность алгоритмов sort, parallel_sort, parallel_buffered_sort и parallel_radixsort при одном и том же большом наборе случайных данных.

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

В этом примере предполагается, что во время сортировки допустимо выделить пространство O(N) лучше parallel_radixsort всего в этом наборе данных на этой конфигурации компьютера.

[В начало]

См. также

Заголовок	Description
Практическое руководство. Написание цикла parallel_for	Показывает, как использовать parallel_for алгоритм для умножения матрицы.
Практическое руководство. Написание цикла parallel_for_each	Показывает, как использовать parallel_for_each алгоритм для вычисления количества простых чисел в объекте std::array параллельно.
Практическое руководство. Использование функции parallel_invoke для написания программы параллельной сортировки	Показывается, как использовать алгоритм parallel_invoke для повышения производительности алгоритма битонной сортировки.
Практическое руководство. Использование функции parallel_invoke для выполнения параллельных операций	Показывается, как использовать алгоритм parallel_invoke для повышения производительности программы, выполняющей несколько операций с общим источником данных.
Практическое руководство. Параллельное выполнение операций сопоставления и сокращения числа элементов	Демонстрируется использование алгоритмов parallel_transform и parallel_reduce для выполнения операций сопоставления и редукции, которые подсчитывают вхождения слов в файлах.
Библиотека параллельных шаблонов	Описывает PPL, которая предоставляет императивную модель программирования, которая способствует масштабируемости и простоте использования для разработки параллельных приложений.
Отмена в библиотеке параллельных шаблонов	Объясняет роль отмены в PPL, как отменить параллельную работу и как определить, когда группа задач отменена.
Обработка исключений	Объясняет роль обработки исключений в среде выполнения параллелизма.

Справочные материалы

Функция parallel_for

Функция parallel_for_each

Функция parallel_invoke

Класс affinity_partitioner

Класс auto_partitioner

Класс simple_partitioner

Класс static_partitioner

Функция parallel_sort

Функция parallel_buffered_sort

Функция parallel_radixsort