Параллелизация с декомпозицией задачи и декомпозицией области. Примеры

Декомпозиция — это процесс разбиения задачи и ее решения на части. Иногда части группируются в логические области (т.е. поиск, сортировка, вычисление, ввод и вывод данных и т.д.). В других случаях части группируются по логическим ресурсам (т.е. файл, связь, принтер, база данных и т.д.). Существует три основных варианта декомпозиции: простая декомпозиция (trival), функциональная (functional) и декомпозиция данных. Вопрос об использовании того или иного типа декомпозици при написании параллельной программы решается исходя из структуры самой задачи. Причем, в зависимости от условий, можно использовать сразу несколько типов.

Тривиальная декомпозиция

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

Функциональная декомпозиция

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

Предположим наша задача сводится к применению некоего функционального оператора к большому массиву данных: S[i]=F(a[i]). Предположим также, что выполнение функции F над одним элементом массива занимает достаточно большое время и нам хотелось бы это время сократить. В этом случае мы можем попытаться представить исходную функцию как композицию нескольких функций: S(a[i])=I(H(R(a[i]).Произведя декомпозицию мы получим систему последовательных задач: x=r(a[i]);
y=h(x); b[i]=i(y); Каждая из этих задач может быть выполнена на отдельном узле кластера. Как можно заметить общее время обработки одного элемента массива a[i] в результате не изменяется, а скорее немного увеличивается за счет межпроцессорных пересылок. Однако общее время обработки всего массива заметно снижается за счет того, что в нашем примере одновременно идет обработка сразу трех элементов массива.

У данного метода декомпозиции есть пара особенностей, о которых надо помнить.

Первая особенность сосотоит в том, что выход кластера на максимальную эффективность происходит не сразу после запуска задачи, а постепенно, по мере того, как происходит частичная обработка первого элемента массива. Второй и третий процессоры в нашем примере, которые отвечают за выполнение функций g(x) и f(y), будут простаивать до тех пор, пока не закончится выполнение функции h(a[1]) на первом процессоре. Третий процессор будет простаивать до окончания выполнения функции g(a[1]). По аналогичному сценарию, только в зеркальном отображении, происходит окончание работы.

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

Декомпозиция данных

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

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