glava3 4 (Лобусов Е.С. Теоретические основы параллельных вычислений), страница 4

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

Для найденного списка приоритетов теперь организуется конкретный вариант линейного порядка для вершин каждого подграфа: упорядочиваются вершины в порядке убывания приоритета.

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

Добавим к графу G_А исходную (нулевую) вершину с номером равным 0 и нулевым весом и соединим исходную вершину со всеми другими вершинами G_А , не имеющими входных дуг. Теперь в графе G_А имеется нулевая вершина и конечная вершина (рис.3.4г). Следовательно можно построить расписание и найти длину расписания как длину критического пути из 0 вершины в конечную вершину.

Компонента t_i для двойственных вершин обмена должна обязательно иметь одно и тоже значение (она выбирается как наибольшее из 2-х полученных значений для двойственных вершин); выбор только одного значения t_i из двух объясняется одновременностью начала обмена между двумя процессорами. Причем, если оказывается, что критический путь проходит через дугу обмена, то учитывается вес только одной из двойственных вершин.

На рис.3.4г в исполняемом графе G_А двойственные вершины обмена обозначены одним номером, но один из них со штрихом.

На простом примере покажем, что полученное таким образом расписание характеризует только граф G_А , но не граф G_А .

Допустим, что имеется граф алгоритма обработки G_А с известными весами вершин(указаны внутри), который дан на рис.3.5а. Оптимальное распределение согласно (12) компонент (вершин G_А) на сеть из 2-х одинаковых процессоров, не принимая во внимание время на обмен между процессорами, приводит к матрицам S и Q.

;

(веса приведены в вершинах графа) с показателем качества J = 7.

Линейное упорядочивание согласно графу на рис.3.5б с учетом весов вершин в подграфах (рис.3.5в) дает следующий исполняемый граф G_А (рис.3.5г). Оценка длины расписания дает значение равное 8 больше, чем значение показателя качества равное 7. Используя другой линейный порядок (рис.3.5е) имеем исполняемый граф рис.3.5д, с показателем качества равным 7. Тем самым, для разных линейных порядков графа при одном и том же распределении компонент имеем разные решения.

В то же время можно предложить вариант, который будет давать наилучшее решение. На рис.3.5а этот наилучший вариант распределения указан пунктиром и ему соответствует линейный порядок (з) и исполняемый граф (ж). Длина расписания будет равна 5 (это максимальная длина графа G_А), хотя ему будет соответствовать значение показателя распределения J = 9.

3.1.2.1 Составление расписания для процессоров с совмещением операций ввода-вывода.

В соответствии с принятой моделью процессора с совмещением операций и ВВ и параллельно работающими каналами (см. 2.3.1) возникает дополнительный процессор для обмена. Поэтому возникающие в графе G_А вершины обмена теперь не будут иметь двойственной принадлежности. Применительно

к примеру на рис.3.4а вершины обмена 10, 11, 12 действительно являются равноправными со всеми другими. Матрица S становится теперь размера (m + n_c)(n + n_c) (рис.3.4д). Исполняемый граф незначительно модифицируется по сравнению с уже полученным (рис.3.4г). На рис.3.4е приведен данный вариант исполняемого графа; вершина 13 является промежуточной и соответствует операции ввода и хранения данных, поступающих от канала 10 и их п
оследующей передачи в канал 11.

Рис.3.5

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

3.1.2.2 Составление расписания для процессоров с совмещением операций ввода-вывода и квазипараллельной работой (обработкой)

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

Для квазипараллельных процессоров теперь нет необходимости в предварительном линейном упорядочивании операций, составляющих алгоритм обработки. То есть на квазипараллельном процессоре возникает возможность исполнить исходную непреобразованую структуру алгоритма обработки (расширенный граф G'_A).

Квазипараллельный процессор типа транспьютера является аппаратной поддержкой параллельной программы на языке OCCAM. Это является чрезвычайно интересным и важным моментом. Совместно с совмещением операций ВВ и параллельным функционированием 4-х каналов ввода-вывода данный квазипараллельный процессор – эффективное средство обработки.

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

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

Квазипараллельная обработка усложняет процедуру составления расписания, так как теперь условие 3 из (23) не выполняется. Но, тем не менее, реально составить алгоритм нахождения max пути в графе обработки с квазипараллельным режимом работы в каждом процессоре.

3.2 Динамические методы.

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

• зависимостью времени выполнения компонент алгоритма от данных;

• наличием асинхронно взаимодействующих с внешней средой каналов связи и частей алгоритма;

• выходом нескольких процессоров сети из строя.

На рис.3.6 приведена функциональная схема динамического распределения. Она включает в себя: блок нахождения начального распределения; блок текущего измерения состояния процессов и процессоров; блок вычисления обобщённых характеристик процессов и процессоров и блок внесения изменений в текущее (существующее) распределение.

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

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

Решение задачи динамического перераспределения открывает многочисленные пути поиска и исследований.

В [7] обсуждается перечисленные выше вопросы динамического распределения и предлагаются определённые решения для них, а в [8], исследуется вполне определённый алгоритм динамической загрузки, называемый диффузным.

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

Сделаем предположение, что все n компонент алгоритма обработки выполняются параллельно и распределяются на известную сеть из m процессоров (т.е. не учитывается параллельно-ярусная структура алгоритма обработки). Тогда нетрудно получить следующую математическую формулировку:

(25)

Общее число переменных (n + 2)m + 1, из них nm - бинарных, общее число ограничений типа равенство (n + 2m).

Примем параметр  = 0. Тогда вся задача (пере)распределения сводится к задаче смешанного булевого линейного программирования.

Предварительный анализ нахождения решения (25), используя симплекс-метод, позволяет предложить процедуру поиска решения варьированием только бинарных переменных из (25)*, так как остальные оставшиеся переменные (за исключением одной) необходимо включать в число базовых.

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

На каждом шаге, начиная с начального распределения, происходит поиск из группы уравнений (25)*** одного, для которого дополнительная переменная при некотором j = k становится равной нулю . Все остальные дополнительные переменные являются неотрицательными. Тем самым система уравнений (25)*** принимает вид:

(26)

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

После переноса в k-ое уравнение найденной вычислительной загрузки происходит приведение полученной системы уравнений к виду (26). Далее опять повторяется процесс поиска перемещаемой вычислительной загрузки и т.д. до нахождения . Останов алгоритма происходит по некоторому условию, связанному с анализом значений дополнительных переменных.

Учёт коммуникационной загрузки увеличивает существенно сложность расчётов.