Блок задач

11. Многопоточность

Сложность 4

Задача «Алгоритмы min, max»

Постановка задачи

Реализовать обобщенные функции pmin_element и pmax_element, которые являются многопоточными версиями функций std::min_element и std::max_element.

Многопоточность должна быть реализована как с помощью потоков (std::thread) так и с помощью асинхронных функций (std::async). Способ параллелизма должен определяться с помощью ExecutionPolicy классов (наподобие как это сделано в stl). Определение количества потоков выполнения и асинхронных функций является деталью реализации. Нижеприведенные сигнатуры функций pmin_element и pmax_element фиксированы и не подлежат изменению.

//pminmax.hpp
template< class ExecutionPolicy, class ForwardIt >
ForwardIt pmin_element( ExecutionPolicy&& policy,
                       ForwardIt first, ForwardIt last );

template< class ExecutionPolicy, class ForwardIt, class Compare >
ForwardIt pmin_element( ExecutionPolicy&& policy,
                       ForwardIt first, ForwardIt last, Compare comp );

template< class ExecutionPolicy, class ForwardIt >
ForwardIt pmax_element( ExecutionPolicy&& policy,
                       ForwardIt first, ForwardIt last );

template< class ExecutionPolicy, class ForwardIt, class Compare >
ForwardIt pmax_element( ExecutionPolicy&& policy,
                       ForwardIt first, ForwardIt last, Compare comp );

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

Требования

  1. Сигнатуры функций pmin_element и pmax_element фиксированы и не подлежат изменению.
  2. Названия header и source файлов следующие: pminmax.hpp.
  3. Написать unit test'ы для реализованных функций.
  4. Провести замеры времени выполнения функций для сравнения параллельной версии и последовательной.