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

  • Статья

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

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

Подразделы

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

  • Алгоритм parallel_for

  • Алгоритм parallel_for_each

  • Алгоритм parallel_invoke

Алгоритм parallel_for

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

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

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

Многие циклы 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();
   });
}

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

1 2 4 3 5

Так как алгоритм 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(values.begin(), values.end(), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

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

4 5 1 2 3

Так как алгоритм 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;
}

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

108 11.2 HelloHello

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

[в начало]

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

Ссылки

Функция parallel_for

Функция parallel_for_each

Функция parallel_invoke