13. Проектирование параллельных алгоритмов. 4 этапа. Характеристика этапов.

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

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

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

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

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

3. Укрупнение. Задачи и взаимосвязи, определенные на первых 2-х этапах, оцениваются с точки зрения производительности и затрат на реализацию. При необходимости, задачи объединяются в более крупные для повышения производительности либо для снижения затрат.

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

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

13. Декомпозиция – основная задача. 2 метода. Контрольные вопросы.

Задача этой стадии – выявить все возможности распараллеливания задачи. Поэтому задача разбивается на как можно большее число подзадач. Это обеспечивает макс гибкость на след этапах.

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

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

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

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

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

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

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

3. Одинаковы ли задачи по размеру? Если нет, не удастся равномерно распределить работу по процессорам.

4. Имеется ли несколько вариантов разбиения? Для увеличения гибкости рекомендуется рассмотреть альтернативы заранее, используя как доменную, так и функциональную декомпозиции.

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