Проектирование параллельных алгоритмов.

 

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

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

 

 

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

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

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

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

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

 

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

 

Декомпозиция.

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

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

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

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

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

Рассмотрим пример.

 

Допустим, это модель атмосферы. Возможна 1-мерная, 2-мерная и 3-мерная декомпозиции. Поскольку мы на данном этапе стремимся получить как можно более глубокую декомпозицию, выбираем 3-мерную. Каждая подзадача имеет набор данных, описывающих ее состояние, и отвечает за обновление этого состояния. Другой пример – умножение матрицы на вектор или метод Гаусса.

 

Теперь рассмотрим другой пример – метод алгоритма поиска..

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

Еще один пример – декомпозиция модели климата.

 

 

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

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

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

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

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

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

 

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

Как правило, коммуникации между задачами описываются в терминах каналов, по которым задача может передавать и принимать информацию. Тогда определение коммуникаций включает 2 фазы. Вначале определяется структура каналов, которые связывают (непосредственно или опосредованно) задачи-потребители информации с задачами-поставщиками информации. Затем мы определяем сообщения, которые могут посылаться от одной задачи другой по этим каналам. В зависимости от реализации сами каналы могут и не создаваться. Например, в модели параллелизма данных каналы в явном виде не используются. Тем не менее, явное описание коммуникаций помогает количественной оценке эффективности алгоритма с учетом понятий локальности и затрат на коммуникации.

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

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

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

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

- локальные / глобальные коммуникации: при локальных коммуникациях задача обменивается данными с необходимым количеством других задач (соседей); при глобальных – с множеством других задач.

- структурированные / неструктурированные – при структурированных коммуникациях задачи и их соседи образуют регулярную структуру; при неструктурированных это может быть произвольный граф.

- при статических коммуникациях индивидуальности партнеров не меняются; при динамических – могут изменяться

- при синхронных коммуникациях поставщики и потребители обмениваются информацией согласованно, при асинхронной этого не требуется.

 

Локальные коммуникации.

В качестве примера задачи с локальными коммуникациями рассмотрим метод конечных разностей Якоби. В этом методе значения в узлах многомерной решетки периодически обновляется с учетом значений в некотором определенном количестве соседних узлов. Набор значений, необходимый для определения одного конкретного значения, называется stencil. Так, для двухмерной решетки с обновлением по 5 точкам используется такое выражение:

Структура задач и каналов.

 

 

Каждая задача выполняет след логику:

 

for t=0 to T-1

 

send to each neighbor

 

receive , , , from neighbors

 

compute using Equation 2.1

 

endfor

 

Как уже говорилось, лучший параллельный алгоритм может отличаться от лучшего последовательного.

Это справедливо и для данного случая. При последовательном расчете лучшие результаты дает схема Гаусса-Зейделя. В этой схеме элементы вычисляются в определенном порядке, который обеспечивает использование последних значений других элементов:

 

 

Однако, в случае параллельного выполнения эта схема не столь удобна. Если в схеме Якоби все вычисления могут выполняться параллельно, то здесь одновременно могут выполняться только N/2 точек из N². Поэтому при параллельных вычислениях используют некоторые модификации схемы Гаусса-Зейделя, например, шахматную схему:

 

 

Глобальные коммуникации.

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

 

Если мы примем такую схему, мы получаем одну «управляющую» задачу, которая собирает данные от остальных и выполняет суммирование. Но, поскольку одновременно «управляющая» задача может принимать только одно значение, время суммирования N чисел будет порядка N – не очень удачно!

Этот пример иллюстрирует две принципиальные проблемы, возникающие при разработке алгоритма, исходя из «чисто локального» подхода к коммуникациям:

1. алгоритм централизован – вычисления и данные не распределены. Одна из задач участвует во всех операциях.

2. алгоритм «существенно последовательный» - не удается достичь одновременности выполнения.