Параллельное программирование на С++ в действии полностью

Если же процессорных ядер очень много (столько же, сколько элементов в списке, или больше), то описанный подход оказывается не столь эффективен. Если разбить всю работу между процессорами, то на первом шаге каждый процессор будет работать всего с двумя элементами. Но тогда на этапе распространения результатов большинство процессоров будут ждать, и хорошо бы их чем-то запять. В таком случае можно подойти к задаче по-другому. Вместо того чтобы сначала вычислять частичные суммы всех блоков, а затем распространять их от предыдущего к следующему, мы можем распространять суммы по частям. Сначала, как и раньше, вычисляем суммы соседних элементов. На следующем шаге каждое вычисленное значение прибавляется к элементу, отстоящему от него на расстояние 2. Затем новые значения прибавляются к элементам, отстоящим на расстояние 4, и так далее. Если начать с тех же самых девяти элементов, то после первого шага мы получим последовательность 1, 3, 5, 7, 9, 11, 13, 15, 17, в которой правильно вычислены первые два элемента. После второго шага получается последовательность 1, 3, 6, 10, 14, 18, 22, 26, 30, в которой правильны первые четыре элемента. После третьего мы получим последовательность 1, 3, 6, 10, 15, 21, 28, 36, 44, в которой правильны первые восемь элементов. И после четвертого шага получаем окончательный результат 1, 3, 6, 10, 15, 21, 28, 36, 45. Общее количество шагов здесь больше, чем в первом варианте, зато и возможности для распараллеливания на большое число процессоров шире — на каждом шаге каждый процессор может обновлять одно число.

Всего во втором варианте требуется выполнить log₂(N) шагов по N операций на каждом шаге (по одной на процессор), где N — число элементов в списке. В первом же варианте каждый поток производит N/k операций для вычисления частичной суммы своего блока и еще N/k операций для распространения сумм (здесь k — число потоков). Следовательно, вычислительная сложность первого варианта в терминах количества операций составляет O(N), а второго — O(N log(N)). Однако, если процессоров столько же, сколько элементов в списке, то во втором варианте требуется произвести только log(N) операций на каждом процессоре, тогда как в первом при большом k операции из-за распространения частичных сумм вперед фактически сериализуются. Таким образом, если количество процессоров невелико, то первый алгоритм завершится быстрее, тогда как в массивно параллельных системах победителем окажется второй алгоритм. Это крайнее проявление феномена, обсуждавшегося в разделе 8.2.1.

Но оставим в стороне эффективность и перейдем к коду. В листинге 8.11 приведена реализация первого подхода.

Листинг 8.11. Параллельное вычисление частичных сумм путём разбиения задачи на части

template

void parallel_partial_sum(Iterator first, Iterator last) {

 typedef typename Iterator::value_type value_type;

 struct process_chunk { ←(1)

  void operator()(Iterator begin, Iterator last,

   std::future* previous_end_value,

   std::promise* end_value) {

   try {

    Iterator end = last;

    ++end;

    std::partial_sum(begin, end, begin); ←(2)

    if (previous_end_value) {            ←(3)

     value_type& addend = previous_end_value->get();←(4)

     *last += addend;              ←(5)

     if (end_value) {

      end_value->set_value(*last); ←(6)

     }

     std::for_each(begin, last, [addend](value_type& item) {←(7)

      item += addend;

     });

    } else if (end_value) {

     end_value->set_value(*last); ←(8)

    }

   } catch (...) { ←(9)

    if (end_value) {

     end_value->set_exception(std::current_exception()); ←(10)

    } else {

     throw; ←(11)

    }

   }

  }

 };

 unsigned long const length = std::distance(first, last);

 if (!length)

  return last;

 unsigned long const min_per_thread = 25; ←(12)

 unsigned long const max_threads =

  (length + min_per_thread - 1) / min_per_thread;

 unsigned long const hardware_threads =

  std::thread::hardware_concurrency();

 unsigned long const num_threads =

  std::min(

   hardware_threads!= 0 ? hardware_threads : 2, max_threads);