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

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

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

Подразделы

• Алгоритм parallel_for

• Алгоритм parallel_for_each

• Алгоритм parallel_invoke

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

  • Алгоритм parallel_transform

  • Алгоритм parallel_reduce

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

• Секционирование работы

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

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

Алгоритм parallel_for

Алгоритм concurrency::parallel_for многократно параллельно выполняет одну и ту же задачу. Все эти задачи параметризованы значением итерации. Этот алгоритм полезен при наличии тела цикла, в котором отсутствует совместное использование ресурсов различными итерациями этого цикла.

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

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

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

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

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

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

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

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

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

Примечание

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

Пример

В следующем примере показана основная структура алгоритма 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();
   });
}

В данном примере получается следующий результат.

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

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

[Наверх]

Алгоритм parallel_for_each

Алгоритм concurrency::parallel_for_each параллельно выполняет задачи в итеративном контейнере, например предоставленные библиотекой STL. В нем используется такая же логика секционирования, что и в алгоритме parallel_for.

Алгоритм parallel_for_each похож на алгоритм std::for_each из библиотеки STL, но алгоритм 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
*/

В данном примере получается следующий результат.

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

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

[Наверх]

Алгоритм parallel_invoke

Алгоритм concurrency::parallel_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;
}

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

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

[Наверх]

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

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

Важно!

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

Алгоритм 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;
    words.push_back(L"Lorem ");
    words.push_back(L"ipsum ");
    words.push_back(L"dolor ");
    words.push_back(L"sit ");
    words.push_back(L"amet, ");
    words.push_back(L"consectetur ");
    words.push_back(L"adipiscing ");
    words.push_back(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.

Пример. Параллельное выполнение сопоставления и уменьшения

Операция сопоставления применяет функцию к каждому значению в последовательности. Операция редукции объединяет элементы последовательности в одно значение. Можно использовать классы STL std::transform std::accumulate для операций сопоставления и редукции. Однако для многих задач можно использовать алгоритм 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, но повышает эффективность кэша способом сопоставления диапазонов в рабочие потоки. Этот тип разделения может повысить производительность, если цикл выполняется над тем же набором данных несколько раз (например, цикл в цикле) и данные подходят для кэша. Этот разделитель не полностью участвует в отмене. Он также не использует согласованную семантику блокировки и поэтому не может использоваться с параллельными циклами с впередиидущей зависимостью.

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

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

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

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

Алгоритмы parallel_for_each и parallel_transform поддерживают только контейнеры, которые используют итераторы произвольного доступа (например, std::vector) для статического, простого и разделителя сходства.Использование контейнеров, использующих двунаправленные и прямые итераторы, вызывает ошибку времени компиляции.Разделитель по умолчанию, 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 как не const l-value ссылку, чтобы алгоритм мог сохранять состояние для последующих циклов для повторного использования. В следующем примере демонстрируется базовое приложение, которое параллельно выполняет одну и ту же операцию над набором данных несколько раз. Использование 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 предоставляет 3 алгоритма сортировки: concurrency::parallel_sort, concurrency::parallel_buffered_sort и concurrency::parallel_radixsort. Эти алгоритмы сортировки полезны, если имеется набор данных, который выгоднее сортировать параллельно. В частности, параллельные сортировки полезны при наличии большого набора данных или при использовании вычислительно затратных операциях сравнения. Каждый из этих алгоритмов сортирует по месту.

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

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

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

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

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

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

Совет

Эти параллельные сортировки поддерживают семантику перемещений.Можно определить перемещающий оператор присваивания для более эффективного выполнения операции обмена.Дополнительные сведения о семантике перемещения и перемещающем операторе присваивания см. в разделе Декларатор ссылки Rvalue: && и Практическое руководство. Написание конструктора перемещений.Если вы не предоставите перемещающий оператор присваивания или функцию обмена, алгоритмы сортировки используют копирующий конструктор.

В следующем базовом примере показано использование 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::complex<double> в порядке возрастания.

// 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 может выполняться эффективнее. Лучшим способом для определения наиболее подходящего алгоритма сортировки в любом исходном сценарии является проверка и измерение длительности сортировки типичных данных при обычной конфигурации компьютера. Ниже приведены рекомендации по выбору стратегии сортировки.

• Размер набора данных. В этом документе небольшой набор данных содержит элементы менее 1,000 элементов, средний набор данных содержит между 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 выполняется лучше на этом наборе данных на этой конфигурации компьютера.

[Наверх]

Связанные разделы

Название	Описание
Практическое руководство. Написание цикла 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