|
4.3. Общая схема этапов разработки параллельных алгоритмов
В учебном пособии [3] описана технология подготовки параллельных
приложений в виде следующих этапов:
1.
Декомпозиция задачи на подзадачи, которые реализуются
независимо.
2.
Определение
для
сформированного
набора
подзадач
информационных взаимодействий.
3.
Масштабирование подзадач, определение количества процессоров.
4.
Определение архитектуры системы, закрепление подзадач за
процессорами, составление расписания.
После выполнения указанных этапов и оценки качества параллельного
алгоритма (ускорения, эффективности, масштабируемости) может оказаться
необходимым повторение некоторых (или всех) этапов [3]. Если в результате
ряда попыток желаемые показатели качества не достигаются, следует
проанализировать и, возможно, изменить математическую постановку задачи с
целью построения новой вычислительной схемы.
Следует заметить, что указанная последовательность этапов носит
условный характер. Часто, приступая к разработке параллельного алгоритма,
пользователь ориентируется на конкретную вычислительную систему, в
44
частности, может быть известно возможное число доступных процессоров.
Ясно, что на этапе декомпозиции по данным следует использовать эту
информацию для выбора числа областей, определяющих число подзадач.
Если точное число процессоров неизвестно, но заданы границы
доступного решающего поля, можно начать с масштабирования базового
набора задач, а затем выполнить декомпозицию и выявление связей по
информации. Другими словами, в приведенной общей схеме необходимым
является лишь содержание этапов, в то время как сами этапы могут
выполняться в любой последовательности, притом любой из них может
оказаться как начальным, так и завершающим. На рис. 4.1 показана возможная
схема взаимосвязи типовых этапов разработки алгоритмов параллельных
вычислений.
Рис. 4.1 Общая схема взаимосвязи этапов разработки
параллельных алгоритмов
Если базовые подзадачи определены, установление информационных
зависимостей между ними обычно не вызывает больших затруднений. При
проведении анализа информационных зависимостей между подзадачами
следует различать:
45
o
локальные (на соседних процессорах) и глобальные (в которых
принимают участие все процессоры) схемы передачи данных;
o
структурные
(соответствующие
типовым
топологиям
коммуникаций) и произвольные способы взаимодействия;
o
статические
(задаваемые
на
этапе
проектирования)
или
динамические (определяемые в ходе выполняемых вычислений);
o
синхронные (следующая операция выполняется после выполнения
предыдущей операции всеми процессорами) и асинхронные
способы взаимодействия (процессы могут не дожидаться полного
завершения действий по передаче данных)
Если количество подзадач (областей данных) отличается от числа
процессоров, то необходимо выполнить масштабирование параллельного
алгоритма. Для сокращения количества подзадач укрупняют области исходных
данных, притом в первую очередь объединяют области, для которых
соответствующие подзадачи обладают высокой степенью информационной
взаимозависимости. Если число подзадач меньше числа доступных
процессоров, выполняют декомпозицию. Масштабирование облегчается, если
правила агрегации и декомпозиции параметрически зависят от числа
процессоров.
Распределение подзадач между процессорами очевидно, если количество
областей данных совпадает с числом имеющихся процессоров, а топология сети
передачи данных - полный граф (все процессоры связаны между собой). Если
это не так, подзадачи, имеющие информационные взаимодействия,
целесообразно размещать на процессорах, между которыми существуют
прямые линии передачи данных. Требование минимизации информационных
обменов между процессорами может вступить в противоречие с условием
равномерной загрузки. Решение вопросов балансировки вычислительной
нагрузки значительно усложняется, если схема вычислений изменяется в ходе
решения задачи. При этом необходимо перераспределение базовых подзадач
46
между процессорами (динамическая балансировка) в ходе выполнения
программы.
Центральной проблемой, как уже неоднократно указывалось выше,
является выделение базовых подзадач на этапе декомпозиции. Эта проблема
имеет много аспектов, в следующем разделе кратко рассматриваются лишь
некоторые важнейшие.
Описанная выше схема этапов может использоваться также и для
построения параллельного алгоритма, который характеризуется параллелизмом
задач. При этом содержание этапов может существенно отличаться. В
частности, центральной проблемой в этом случае является выявление взаимно
независимых операторов, которые могут выполняться параллельно и
независимо.
Do'stlaringiz bilan baham: |
