Заполнением E графа G ЯПФ называется сумма

где N - число ярусов в G.

Разбросом Q графа G ЯПФ программы называется сумма

.

Введенные показатели позволяют произвести классификацию ЯПФ. ЯПФ называется равномерной, если в графе G этой ЯПФ дебалансы всехярусовравны нулю.

ЯПФ называется абсолютноравномерной, еслиона равномерна и длины всех ярусов одинаковы.

ЯПФ называется прямоугольной,если разброс в графе этой ЯПФ равен нулю.

ЯПФ называется абсолютно совершенной, если она абсолютно равномерна и прямоугольна.

 

Пример построения ЯПФ алгоритма и расчетее характеристик.

Граф программы задачи, подлежащей решению с помощью многопроцессорной системы, задан в табличной форме (табл. 1.1). В табл. 1.2 указаны длины работ, которые заданы в условных единицах для случая обслуживания процессором с относительной производительностью S₀ =1.

Таблица 1.1.

Выходы работ

Входы работ

Таблица 1.2.

N

Необходимо выполнить:

1) преобразовать граф в ярусно-параллельную форму;

2) рассчитать основные показатели ЯПФ.

1. Преобразование графа в ЯПФ. Пользуясь описанной методикой, представим исходный граф в ярусно-параллельной форме. Для этого выбираем независимые работы. Это работы 1,4,7,12,13. Помещаем их в первый ярус. С этими работами связаны работы 2, 5, 8, 11,14,15, попадающие во второй ярус. Оставшиеся работы 3,6,9 и 10 располагаются в третьем ярусе. Вводим пустую работу в связь, проходящую от 7-й к 9-й работе через 2-й ярус. Результирующая ярусно-параллельная форма приведена на рис.1.3.

рис. 1.3.

Упорядочим обозначения работ в соответствии с принятыми выше. Для этого пронумеруем работы в пределах каждого яруса и проставим полу­ченные номера в нижней части обозначения работы.

Запишем у каждой работы ее длину для случая S₀ = 1

2. Расчет основных показателей ЯПФ.

Ширина ярусов равна:

b¹=5; b²=6; b³=4.

Ширина графа B=6.

Длины ярусов равны:

l¹ = 20; l² = 14; l³ = 11;

Дебалансы ярусов:

d¹ = 20 – 10 = 10;

d² = 14 – 3 = 11;

d³ = 11 – 6 = 5.

Дебаланс графа равен:

10+11+5=26

Заполнение яруса:

E¹ = (20 – 10) + (20 – 15) + (2О – 18) + (20 – 12) = 26;

E² = (14 – 9) + (14 – 5) + (14 – 3) + (14 – 8) + (14 – 11) = 34;

E³ = (11 – 8) + (11 – 6) + (11 – 7) = 12

Заполнение графа:

E =26 + 34 + 12 = 71

Разброс графа:

Q = (6 – 5) + (6 – 4) = 3.

3. ВАРИАНТЫ ЗАДАНИЯ.

По заданной преподавателем букве выбрать матрицу графа по табл. 1.3. – 1.7. По заданному числу из табл. 1.8. выбрать значения трудоемкости работ при обслуживании их процессором с относительной производительностью S_э = 1.

Необходимо выполнить:

1) преобразовать граф в ярусно-параллельную форму,

2) рассчитать основные показатели ЯПФ.

4. ФОРМА ОТЧЕТА.

Отчет должен включать

- вариант задания;

- чертеж полученной ЯПФ;

- расчеты основных характеристик ЯПФ.

 

Таблица 1.3.

вариант А

Выходы работ

Входы работ

Таблица 1.4.

вариант Б

Выходы работ

Входы работ

Таблица 1.5.

вариант В

Выходы работ

Входы работ

Таблица 1.6.

вариант Г

Выходы работ

Входы работ

Таблица 1.7.

вариант Д

Выходы работ

Входы работ

Таблица 1.8.

№ варианта

Длины работ

 

ЗАНЯТИЕ № 2

Определениекритического (длиннейшего) пути ЯПФ.

1. ЦЕЛЬ ЗАНЯТИЯ: практическое закрепление знаний об определении нижней границы возможного времени реализации программы.

2. ОСНОВНЫЕ СВЕДЕНИЯ.

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

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

Нумеруем работы а пределах каждого яруса f: i^f= 1^f, 2^f,… b^f

Для определения критического пути воспользуемся алгоритмом нахожде­ния пути в графе с дугами произвольной длины. Преобразуем граф G к се­тевому, для этого введем нулевой ярус f = 0 и поместим туда фиктивную вершину X, которую соединим дугами со всеми вершинами первого яруса и присвоим каждой дуге длину равную длительности соответствующей вершины. Так, дуге (X, l¹) присваивается длина l¹, равная трудоемкости этой вершины. Дугам, соединяющим (f – 1) -й ярус с f- м ярусом, присваивается длины равные трудоемкости соответствующих работ f- го яруса. Все вершины N -го яруса соединяются с единственной вершиной Z в фиктивном (N + 1) -м ярусе, и имеют длину равную нулю.

В результате такого преобразования получим сетевой граф G` с исто­ком Х и стоком Z. Исходная задача сводится к нахождению длиннейшего пути в сети G`.

Алгоритм вхождения экстремального путина сети G` заключается в следующем

1. Вершину Х помечаем индексом L ₀ = 0, остальные X_i помечаем индек­сом L _i = 0.

2. Ищем такую дугу (X_i, X_j), для которой L _j – L _i < l(X_i, X_j) и заменяеминдекс L _j индексом L '_j= L _i+l(X_i, X_j). Продолжаем этот процесс до тех пор пока можно увеличить индекс хотя бы одной вершины.

3. Находим длиннейший путь, начиная с вершины Z. Для этого находим вершину Х_р1 инцидентную Z, для которой выполняется условие L _z – L _p1 = l(Х_р1 , Z). Далее находим Х_р2 инцидентную Х_р1, для которой выполняется условие L _р1 - L _р2 = l(Х_р2 , Х_р1) и так до тех пор пока не дойдем до вершины X: Экстремальный путь Mэ = (X, Х_рn ,…, Х_р2 , Х_р1, Z) длина которого L _z является максимальной.

Пример нахождения критического пути ЯПФ алгоритма

Определим критический путь для ЯПФ алгоритма, которая приведена на рис.1.3. Построим сеть по данной ЯПФ, как было описано выше. Полученная сеть G` представлена на рис. 2.1. Согласно алгоритму помечаем вершину Х индексом 0, индекс ¥ у остальных вершин не ставим, чтобы рисунок был нагляднее. При изменении индекса старый будем зачеркивать и справа писать новый.

рис. 2.1.

 

Процесс изменения индексов виден из рис. 2.2. Полученный критический путь М₀ = (X, 12, 8, 6, Z), его величина Ткр = L z = 40.

рис. 2.2.

 

3. ВАРИАНТЫ ЗАДАНИЯ.

По заданной преподавателей букве выбрать матрицу графа программы по табл. 1.3 – 1.7. По заданной цифре из табл. 1.8. выбрать значения трудоемкости работ при обслуживании их процессором с относительной про­изводительностью Sэ = 1.

Необходимо выполнить:

1) преобразовать граф в ярусно-параллельную форму;

2) построить по графу ЯПФ G сеть G`;

3) определить на сети G` критическийпуть М₀ изначение Ткр.

4. ФОРМА ОТЧЕТА.

Отчет должен включать:

- вариант задания;

- чертеж полученной ЯПФ;

- чертеж сети G`;

- критический путь М₀ и значение Ткр.

ЗАНЯТИЕ №3

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

1. ЦЕЛЬ ЗАНЯТИЯ: практическое закрепление знаний о распределении загрузки между процессорами многопроцессорной системы.

2. ОСНОВНЫЕ СВЕДЕНИЯ.

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

а) относительная производительность процессоров:

,

где l^f_iэ, i = 1, 2, …, b^f, f = 1, 2, …, N, длина (трудоемкость) i -той работы в f -м ярусе при обслуживании ее с помощью некоторого эталонного процессора, для которого принято Sэ=1, Sm – относительная производительность m -го процессора m = 1, 2, …, n.

б) - длительность обслуживания с помощью n процессоров работ f -го яруса ЯПФ; этот показатель оценивается длительностью работы наиболее загруженного процессора на f -м ярусе;

в) - длительность решения всей задачи (обслуживание всех работ ЯПФ):

,

г) Т^f пр.m. - длительность простоя m -го процессора при обслуживании операторов f -го яруса;

Т^f пр.m. = - , m=1, 2, …, n,

где - загруженность m -го процессоре на f -м ярусе;

д) суммарные простои процессоров:

- на f- м ярусе;

- при обслуживании ЯПФ;

е) коэффициент простоя процессоров:

;

ж) средняя относительная производительность одного процессора системы:

;

з) повышение производительности системы за счет организации параллельных вычислений на n процессорах:

Пусть на некотором этапе решения задачи, соответствующей обработке f -го яруса имеется b^f работ, принадлежащих f -му ярусу, и n про­цессоров, входящих в ВС. Будем считать, что каждая из работ может быть выполнена на одном из процессоров. Процессоры могут иметь различную производительность.

Показатели относительной производительности процессоров представим в виде множества S = {S₁, S₂, …, S_n}. Располагаем процессоры в список по мере убывания их производительности: П = {П₁, П₂,...,П_n}, где процессор П_i характеризуется:

;

Располагаем также в список по мере убывания длины работ, находящихся в рассматриваемом f- м ярусе:

, где работа x^fi характеризуется длиной:

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

Если n>b^f, то неиспользованными остаются процессоры, имеющие на­именьшую производительность.

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

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

 

Пример распределения загрузки.

В качестве примера распределим загрузку для реализации алгоритма, заданного ЯПФ (рис. 3.1). Алгоритм будет реализовываться на вычислительной системе состоящей из шести параллельно работающих процессоров, относительная производительность которых, по сравнению с эталонным, производительность которого принята за единицу, приведена в табл. 3.1.

рис. 3.1.

Таблица 3.1

N проц-ра	П2	П3	П4	П5	П6	П1
Sm	1.6	1.3		0.8	0.6	0.3
f=1	i1	31	41	21	51	11
l1im	12.5	13.8			16.7
f=2	i2	32	62	12	52	22	42
l2im	8.8	8.5		11.3	8.4
f=3	i3	23	13	43	33
l3im	6.9	6.2		7.5

 

Рассчитаем длины работ с учетом их реализации на процессоре m -го типа по формуле:

,

где l^fiэ – время реализации работы на процессоре, производительность которого принята за эталонную Sэ = 1. Используя методику решения данной задачи, изложенную выше, заполним табл. 3.1. Наиболее трудоемкая работа оказывается распределенной на наиболее производительный процессор.

Теперь длины ярусов l¹ = T¹реш = 18.7, l² = T²реш = 11.3, l³ = T³реш = 7.5, где T^fреш – время решения на f- м ярусе, f = 1,2,3.

В результате имеем:

а) время решения задачи в системе:

= 18,7 + 11,3 + 7,5 = 35,5;

б) суммарные простои процессоров:

= 27,2 + 11,8 + 17,4 = 56,4;

в) коэффициент простоя процессоров:

;

г) повышение производительности системы по сравнению со случаем использования одного процессора:

3. ВАРИАНИЫ ЗАДАНИЯ

По заданной преподавателем первой букве выбрать матрицу графа программы по табл. 1.3. - 1.7. По заданной цифреиз табл. 1.8 выбрать значения трудоемкости работ при обслуживании их процессором с относительной производительностью Sэ = 1. По заданной второйбукве выбрать относительные производительности процессоров из табл. 3.2.

Та