Программирование для параллельных вычислительных систем
Параллельная форма алгоритма
Для реализации алгоритма на параллельной системе его следует представить в виде последовательности групп операций.
Отдельные операции в каждой группе должны обладать следующим свойством: их можно выполнять одновременно на имеющихся в системе функциональных устройствах.
Итак, пусть операции алгоритма разбиты на группы, а множество групп полностью упорядоченно так, что каждая операция любой группы зависит либо от начальных данных, либо от результатов выполнения операций, находящихся в предыдущих группах.
Представление алгоритма в таком виде называется параллельной формой алгоритма. Каждая группа операций называется ярусом, а число таких ярусов - высотой параллельной формы. Максимальное число операций в ярусах (число привлекаемых процессов в ярусах) - шириной параллельной формы.
Один и тот же алгоритм может иметь много параллельных форм. Формы минимальной высоты называются максимальными.
Представление и реализация алгоритмов
Реализация алгоритма на вычислительной системе - это реализация базовой программы эквивалентным способом. Поэтому (явно или неявно) должны быть определены:
функция, устанавливающая взаимно однозначное соответствие между вершинами графа алгоритма и отдельно срабатываниями функциональных устройств вычислительной системы;
потоки информации между функциональными устройствами системы;
|
|
|
моменты включения функциональных устройств.
Имеются две основные стратегии при решении этих задач:
статическая;
динамическая.
При статической стратегии решение принимается заранее на основе анализа алгоритма и вычислительной системы, а при динамической стратегии решение принимается в процессе реализации.
Динамическая стратегия характеризует так называемые потоковые линии. Иногда используют смешанные стратегии.
Принято на этой стадии исследования идеализировать ситуацию, предполагая, что система не может сработать и выдать неправильный результат (т.е. результат, относящийся к другому алгоритму): либо система срабатывает и реализует алгоритм, либо система не срабатывает. Этот подход на самом деле во многих случаях весьма далек от истины: например, при решении той или иной вычислительной задачи обычно предполагается, что указанные в алгоритме арифметические действия выполняются точно; однако, при реальных вычислениях компьютерная система реализует «машинную арифметику», так что результат фактически относится к реализации другого алгоритма (причем реализуемый алгоритм, как правило, остается неизвестным).
Соответствие, которое устанавливает упомянутая выше функция между алгоритмом и срабатываниями системы, чрезвычайно важна: ее неудачный выбор может оказаться первой причиной несрабатывания алгоритма. Важно также, чтобы класс «удачных» функций был достаточно широк; иначе, например, может случиться, что в этом классе нет приемлемой функции, которая дает программу с допустимым временем реализации.
|
|
|
Теорема 1.1. Для того чтобы при заданной функции соответствия между вершинами графа алгоритма и отдельными срабатываниями функциональных устройств вычислительной системы алгоритм был реализуем, необходимо и достаточно, чтобы для любых двух вершин, выполняемых на одном функциональном устройстве и связанных путем, более позднее срабатывание соответствовало той вершине, которая находится в конце пути.
Теорема 1.2. Пусть установлена такая функция соответствия между вершинами графа алгоритма и срабатываниями функционального устройства, при которой алгоритм может быть выполнен. Для того чтобы при этой функции алгоритм выполнялся за минимальное время, достаточно, чтобы каждый момент включения функционального устройства совпадал с моментом получения последнего аргумента выполняемой на данном включении операции.
|
|
|
Рассмотрим теперь любую упорядоченную последовательность вершин графа алгоритма, в которой для каждой пары последовательных вершин следующая вершина либо связана дугой с предыдущей, либо обе операции, соответствующие этим вершинам, выполняются на одном функциональном устройстве. Ясно, что операции для этой последовательности вершин могут выполняться лишь последовательно. Значит, при фиксированном соответствии графа алгоритма и соответствующих срабатываниях функционального устройства время реализации алгоритма не меньше, чем минимальное время выполнения (на избранной системе и при том же соответствии) последовательности упомянутых операций.
Определение 1.1. Последовательности с максимальным из минимальных времен выполнения называются максимальными последовательностями.
Благодаря теореме 1.2 легко устанавливаем следующее утверждение.
Теорема 1.3. Пусть установлена функция соответствия между вершинами графа алгоритма и срабатываниями, при которых алгоритм выполним. Тогда минимальное для этой функции время реализации алгоритма равно времени выполнения максимальных последовательностей.
Следствие 1.1. Для того чтобы режим включения функциональных устройств обеспечивал минимальное время реализации алгоритма при данной функции соответствия между вершинами графа алгоритма и срабатывания функциональных устройств, необходимо и достаточно, чтобы время реализации алгоритма было равно минимальному времени выполнения при этой функции соответствия хотя бы одной упорядоченной последовательности операций, каждая из которых либо получает аргумент предыдущей, либо выполняется вместе с предыдущей на одном функциональном устройстве.
|
|
|
Определение 1.2. Режим называется синхронным, если моменты включения функциональных устройств создают равномерную сетку на оси времени, и асинхронным - в противном случае.
Стремление реализовать алгоритм за минимальное время обычно приводит к асинхронному режиму (в особенности, если операции производятся за различное время или на конвейерных функциональных устройствах), однако если время операций одинаково и они производятся на простых функциональных устройствах, то при реализации алгоритма за минимальное время те операции, которые соответствуют максимальной последовательности, будут выполняться в синхронном режиме.
Заметим также, что синхронный режим обычно свойствен процессам, обеспечивающим максимальную загруженность оборудования. Действительно, если система, например, состоит лишь из конвейерных функциональных устройств и работает с полной загруженностью, то включение функциональных устройств обычно происходит с шагом единица.
Модели программирования
Традиционной считается последовательная модель программирования (Рис. 1). В этом случае в любой момент времени выполняется только одна операция и только над одним элементом данных. Последовательная модель универсальна. Ее основными чертами являются применение стандартных языков программирования (для решения вычислительных задач это, обычно, Fortran и С/С++), хорошая переносимость программ и невысокая производительность.
Рис. 1 Модель последовательного программирования
Основными особенностями параллельной модели программирования являются более высокая производительность программ, применение специальных приемов программирования и, как следствие, более высокая трудоемкость программирования, проблемы с переносимостью программ. Параллельная модель не обладает свойством универсальности (Рис. 2).
Рис. 2 Модель параллельного программирования
В параллельной модели программирования появляются проблемы, непривычные для программиста, привыкшего заниматься последовательным программированием. Среди них: управление работой множества процессоров, организация межпроцессорных пересылок данных и другие.
Повышенная трудоемкость параллельного программирования связана с тем, что программист должен заботиться:
· об управлении работой множества процессов;
· об организации межпроцессных пересылок данных;
· о вероятности тупиковых ситуаций (взаимных блокировках);
· о нелокальном и динамическом характере ошибок;
· о возможной утрате детерминизма («гонки за данными»);
· о масштабируемости;
· о сбалансированной загрузке вычислительных узлов.
Дата добавления: 2021-03-18; просмотров: 79; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!