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

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

Существует широкий спектр методов декомпозиции задачи. На следующем рисунке представлена классификация таких методов.

Как видно из рисунка, существует три основных варианта декомпозиции: простая декомпозиция (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. Для уменьшения времени простоя процессоров в ожидании следующей порции работы необходимо таким образом подбирать декомпозированные функции, чтобы время их работы было примерно одинаковым.

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

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

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

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