Распределение по процессорам.

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

Целью распределения является максимальное сокращение времени выполнения. Можно представить себе 2 стратегии:

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

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

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

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

Многие алгоритмы, полученные в результате доменной декомпозиции, предусматривают фиксированное количество задач одинакового размера и структурированные коммуникации. В этом случае задача распределения проста. Мы распределяем задачи так, чтобы снизить объем коммуникаций между процессорами. Мы можем также укрупнить задачи, если это еще не сделано. В итоге получаем P «крупных» задач – по 1 на процессор.

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

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

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

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