C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц

  size_t iterations {0};

  const size_t max_iterations {100000};

  while (abs(z) < 2 && iterations < max_iterations) {

    ++iterations;

    z = pow(z, 2) + c;

  }

  return iterations;

}

4. Далее перед нами часть функции main, которую также не нужно изменять:

int main()

{

  const size_t w {100};

  const size_t h {40};

  auto scale (scaled_cmplx(

    scaler(0, w, -2.0, 1.0),

    scaler(0, h, -1.0, 1.0)

  ));

  auto i_to_xy ([=](int x) {

    return scale(x % w, x / w);

  });

5. В функции to_iteration_count больше не вызываем mandelbrot_iterations(x_to_xy(x)) непосредственно, этот вызов делается асинхронно с помощью std::async:

  auto to_iteration_count ([=](int x) {

    return async(launch::async,

                 mandelbrot_iterations, i_to_xy(x));

  });

6. Перед внесением последнего изменения функция to_iteration_count возвращала количество итераций, нужных конкретной координате, чтобы алгоритм Мандельброта сошелся. Теперь она возвращает переменную типа future, которая станет содержать то же значение позднее, когда оно будет рассчитано асинхронно. Из-за этого требуется вектор для хранения всех значений типа future, добавим его. Выходной итератор, который мы предоставили функции transform в качестве третьего аргумента, должен быть начальным итератором для нового вектора выходных данных r:

  vector<int> v (w * h);

  vector<future<size_t>> r (w * h);

  iota(begin(v), end(v), 0);

  transform(begin(v), end(v), begin(r),

            to_iteration_count);

7. Вызов accumulate, который выводит результат на экран, больше не получает значения типа size_t в качестве второго аргумента, вместо этого он получает значения типа future<size_t>. Нужно адаптировать его к данному типу (если бы мы изначально использовали тип auto&, то этого бы не требовалось), а затем вызвать x.get(), где мы получили доступ к x, чтобы дождаться появления значения.

  auto binfunc ([w, n{0}] (auto output_it, future<size_t> &x)

      mutable {

    *++output_it = (x.get() > 50 ? '*' : ' ');

    if (++n % w == 0) { ++output_it = 'n'; }

    return output_it;

  });

  accumulate(begin(r), end(r),

             ostream_iterator<char>{cout}, binfunc);

}

8. Компиляция и запуск программы дадут результат, который мы видели ранее. Увеличение количества итераций и для оригинальной версии приведет к тому, что распараллеленная версия отработает быстрее. На моем компьютере, имеющем четыре ядра ЦП, поддерживающих гиперпараллельность (что дает восемь виртуальных ядер), я получаю разные результаты для GCC и clang. В лучшем случае программа ускоряется в 5,3 раза, а в худшем — в 3,8. Результаты, конечно, будут различаться для разных машин.

Как это работает

Сначала важно понять всю программу, поскольку далее становится ясно, что вся работа, зависящая от ЦП, происходит в одной строке кода в функции main:

transform(begin(v), end(v), begin(r), to_iteration_count);

Вектор v содержит все индексы, соотнесенные с комплексными координатами, по которым мы итерируем в алгоритме Мандельброта. Результат каждой итерации сохраняется в векторе r.

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

Одним из возможных подходов к распараллеливанию является разбиение всего линейного диапазона от begin(v) до end(v) на фрагменты одного размера и равномерное их распределение между ядрами. Таким образом, все ядра выполнят одинаковый объем работы. Если бы мы использовали параллельную версию функции std::transform с параллельной политикой выполнения, то все бы так и произошло. К сожалению, это неверная стратегия для нашей задачи, поскольку каждая точка множества Мандельброта показывает индивидуальное количество итераций.

Наш подход заключается в том, что мы заполним вектор, в котором содержатся отдельные символы, элементами future, чьи значения будут высчитаны асинхронно. Поскольку вектор-источник и вектор-приемник содержат w*h элементов, что для нашего случая означает 100*40, у нас есть вектор, содержащий 4000 значений типа future, которые высчитываются асинхронно. Если бы наша система имела 4000 ядер ЦП, то это означало бы запуск 4000 потоков, которые выполнили бы перебор множества Мандельброта действительно конкурентно. В обычной системе, имеющей меньшее количество ядер, ЦП будут обрабатывать один асинхронный элемент за другим.

В то время как вызов transform с асинхронной версией to_iteration_count сам по себе не выполняет расчеты, а лишь подготавливает потоки и объекты типа future, он возвращает значение практически мгновенно. Оригинальная версия программы к этому моменту будет заблокирована, поскольку итерации занимают слишком много времени.

Распараллеленная версия программы также может быть заблокирована. Функция, которая выводит на экран все наши значения в консоли, должна получать доступ к результатам, находящимся внутри объектов типа future. Чтобы это сделать, она вызывает функцию x.get() для всех значений. Идея заключается в следующем: пока она ждет вывода первого значения, множество других значений высчитываются одновременно. Поэтому, если метод get() для первого значения типа future возвращается, то следующий объект типа future тоже может быть готов к выводу на экран!

Если размер вектора будет гораздо больше, то возникнет некоторая измеряемая задержка при создании и синхронизации всех этих значений. В нашем случае задержка не так велика. На моем ноутбуке с процессором Intel i7, имеющем четыре ядра, которые могут работать в режиме гиперпараллельности (что дает восемь виртуальных ядер), параллельная версия этой программы работала в 3–5 раз быстрее оригинальной программы. Идеальное распараллеливание сделало бы программу в восемь раз быстрее. Конечно, это ускорение будет различаться для разных компьютеров, поскольку зависит от множества факторов. 

Небольшая автоматическая библиотека для распараллеливания с использованием std::future

Большую часть сложных задач можно разбить на подзадачи. Из всех подзадач можно построить направленный ациклических граф (directed acyclic graph, DAG), который описывает, какие подзадачи зависят друг от друга, чтобы выполнить задачу более высокого уровня. Для примера предположим, что хотим создать строку "foo bar foo bar this that", и можем сделать это только путем создания отдельных слов и их объединения с другими словами или с самими собой. Предположим, что этот механизм предоставляется тремя