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

Библиотека параллельных шаблонов (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), begin(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

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

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

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

Алгоритм parallel_transform

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

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

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

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

В следующем примере показана базовая структура, которая используется для вызова алгоритм parallel_transform.В этом примере инвертирует каждый элемент объекта std::vector в 2 вариантах.Первый способ использует лямбда-выражение.Второй способ используется 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 имеет перегруженные версии 2.Первая принимает один диапазон ввода и унарную функции.Унарная функция может быть лямбда-выражением, принимает один аргумент, объект функции или тип, производный от класса unary_function.Второй принимает 2 диапазона ввода и бинарной функции.Бинарная функция может быть лямбда-выражением, а 2 аргумента, объект функции или тип, производный от 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::transformstd::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 поддерживает все 3 из этих типов итератора.

Обычно эти разделения используются таким же образом, за исключением 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());
}

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

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>

using namespace concurrency;

int wmain()
{    
    // Create an arry 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).

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

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

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

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

Совет

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

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

Хэш-функция должно возвращать целочисленный тип должен быть равен true(std::is_integral::value ).Этот целочисленный тип должен быть преобразуемым строки 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.
*/

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

[Верх]

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

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