6.2.3. Распределение операторов по вм вычислительной системы с распределённой памятью для информационной граф-схемы
При построении плана распределения операторов по ВМ вычислительной системы с распределённой памятью для информационной граф-схемы возникают определённые трудности, связанные с передачей информации через транзитные ВМ. Предлагаемый метод основывается на методе, изложенном в предыдущем разделе. Сущность метода заключается в том, что на первом этапе создаются нити без учёта обмена информацией между ВМ. Затем при построении нитей в моменты обмена данными длины нитей корректируются на время обмена информацией ав данной точке. Вначале получаем модифицированные веса вершин в виде pm,j=pj+qj,i ,где pj – вес j-й вершины, qj,i – вес дуги, исходящей из j-й вершины. При использовании транзитных ВМ модифицированный вес возрастает на qj,i(n-1), где n – количество используемых транзитных процессоров.
4
2 4 3
2 5 1
4 4 4 2 3
3 3 • • • 3 6 4 9
3 2 4 1
3 4 2 5
Рисунок 6.2.8. Граф-схема примера алгоритма решаемой задачи для ВС с распределённой памятью.
Для рассматриваемой граф-схемы определим ранние сроки окончания выполнения операторов без учёта времён обмена информацией между операторами: t1,1=4, t1,2=6, t1,3=9, t1,4=5, t1,5=9, t1,6=9, t1,7=9, t1,8=9, t1,9=9, t1,10=9, t1,11=13, t1,12=16, t1,13=17, t1,14=15, t1,15=18.
Современные структуры ВС могут работать в двух режимах передачи информации. Первый режим характерен тем, что во время выполнения обработки данных, ВМ не может осуществлять передачу информации. Во втором режиме возможна одновременная обработка и передача информации. Рассмотрим первый режим обработки информации.
Учёт времён передачи информации
осуществляется, используя соотношения:
для развёртки – p,j=qi,j+pj,
где j=
–
номера операторов, образующих
развёртку; для свёртки – pj=
qj,i
+pj
где j=
–
номера операторов, образующих cвёртку.
Этим соотношениям удовлетворяют
ранние сроки окончания выполнения
операторов с учётом времён передачи
информации. Модифицированные веса
составят: p1=4, p2=4,
p3=9+2=11,
p4=4+3=7,
p5=7, p6=7,
p7=7, p8=7,
p9=7,
p10=7,
p11=4,
p12=6,
p13=6,
p14=6,
p15=6. Ранние
сроки окончания выполнения составят:t1,1=4,
t1,2=8,
t1,3=15,
t1,4=11,
t1,5=15,
t1,6=15,
t1,7=15,
t1,8=15,
t1,9=15,
t1,10=15,
t1,11=19,
t1,12=25,
t1,13=25,
t1,14=25,
t1,15=25.
Рисунок 6.2.9. Матрица следования с указанием весов дуг и вершин (SDR) для граф-схемы примера алгоритма решаемой задачи для ВС с распределённой памятью
Построим матрицу следования для граф-схемы, показанной на рисунке 6.2.8. В матрице, представленной на рисунке 6.2.9, указаны веса дуг, определяющих времена обмена информацией между указанными операторами, а в 16-ом столбе приведены веса операторов, с помощью которых определяется время выполнения программного модуля. По вычисленным ранним срокам окончания выполнения операторов с учётом передачи информации построим диаграммы решения поставленной задачи.
8 |
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
3 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
2 |
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
||
1 |
1 |
|
|
|
2 |
|
|
|
5 |
|
|
|
|
|
|
11 |
|
|
12 |
|
|
|
|
||
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
Рисунок 6.2.10. Диаграмма ранних сроков окончания выполнения операторов для граф-схемы 6.2.8 с учётом времён передачи информации между операторами. Передача информации показана стрелками.
Алгоритм построения нитей для граф-схемы алгоритма решаемой задачи с учётом времени передачи информации. ВМ может только обрабатывать или только передавать информацию.
Алгоритм построения нитей.
Алгоритм 6.2.1.
1. Просматриваем матрицу SDR по строкам сверху вниз. Если просмотрены все строки, то – конец алгоритма.
2. Если в i-й строке
найдено одно число, то вес i-й
вершины модифицируется к виду: рi:=pi+qj,i
. Если в i-й
строке найдено несколько чисел, то веса
вершин модифицируются следующим
образом: рj:=pj+qi,j
,j={
},
где ,j – множество
столбцов, в которых найдены числа,
qi,j
– множество весов дуг, принадлежащих
i-й строке .
3. Используя модифицированные веса, с помощью алгоритма 6.1.1 вычисляем ранние сроки окончания выполнения операторов.
4. Вычисленные ранние сроки окончания выполнения операторов служат основой для построения диаграммы загрузки ВМ. Каждая строка диаграммы может служить нитью для загрузки в процессор.
Полученные нити разместим на структуре типа обобщённый гиперкуб (см. рисунок 6.2.1), учитывая, что ветви цикла с целью обеспечения минимального времени вычисления цикла должны иметь одинаковое время передачи данных. Находим нить, содержащую начальную вершину граф-схемы. В матрице дистанций определяем строки с минимальными суммами. В данном случае – это 9-я и 11-я строки. Выбираем 9-ю строку. В 9-й строке (9-м ВМ) расположим первую нить. В таблице 6.2.4 эта ситуация отображается символом «+.». Далее пытаемся разместить цикл, который организуется пятым оператором первой нити. На ближайшем расстоянии к 9-й строке находятся 3-й, 7-й, 10-й, 11-й и 15-й столбцы. С помощью этих ВМ можно организовать цикл. Так как самых близких ВМ (расстояние=1) на все нити цикла не хватит, то выбираем еще 2 ВМ с расстоянием до 9-го ВМ равным 2 (1-й и 4-й ВМ). Размещаем на главной диагонали соответствующие нити с указанием её номера и точки. Точка используется для облегчения визуализации нити.
Таблица 6.2.4
-
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
9.
1
1
2
2
3
1
2
2
3
3
4
2
3
3
4
4
5
2
1
0
2
3
1
2
2
1
3
4
2
3
3
2
4
5
3
4
3
1
2
3.
1
1
2
2
3
1
2
2
3
3
4
2
3
3
4
4
2
3
1
10.
2
1
3
4
2
1
3
2
4
5
3
2
4
3
5
2
1
1
2
0
1
3
2
2
3
1
2
4
3
3
4
2
3
6
3
2
2
1
1
0
4
3
3
2
2
1
5
4
4
3
3
2
7
1
2
2
3
3
4
4.
1
1
2
2
3
1
2
2
3
3
4
8
2
1
3
4
2
3
1
0
2
3
1
2
2
1
3
4
2
3
9
2
3
1
2
2
3
1
2
+.
1
1
2
2
3
1
2
2
3
10
3
4
2
1
3
2
2
3
1
6.
2
1
3
4
2
1
3
2
11
3
2
2
3
1
2
2
1
1
2
7.
1
3
2
2
3
1
2
12
4
3
3
2
2
1
3
2
2
1
1
0
4
3
3
2
2
1
13
2
3
3
4
4
5
1
2
2
3
3
4
0
1
1
2
2
3
14
3
2
4
5
3
4
2
1
3
4
2
3
1
0
2
3
1
2
15
3
4
2
3
3
4
2
3
1
2
2
3
1
2
8.
1
1
2
16
4
5
3
2
4
3
3
4
2
1
3
2
2
3
1
0
2
1
17
4
3
3
4
2
3
3
2
2
3
1
2
2
1
1
2
0
1
18
5
4
4
3
3
2
4
3
3
2
2
1
3
2
2
1
1
0
45
45
39
45
39
45
39
39
33
39
33
39
45
45
39
45
39
45
В диагонали таблицы 6.2.4 размещены ВМ, реализующие заданную структуру ВС для решения задачи, представленной граф-схемой на рисунке 6.2.8.
Рассмотрим построение нитей для граф-схемы алгоритма решаемой задачи с учётом времени передачи информации. ВМ может обрабатывать и передавать информацию. В этом случае время решения задачи сравнивается с временем передачи информации и выбирается время, максимальное из этих двух. Граф-схема, представленная на рисунке 6.2.8 в этом случае будет выглядеть следующим образом:
Рисунок 6.2.11. Схема представления обобщенного 3-х мерного гиперкуба 2х3х3. Чёрными точками отмечены ВМ, использованные для решения поставленной задачи
В таблице 6.2.5 представлена матрица следования для граф-схемы примера алгоритма решаемой задачи для ВС с распределённой памятью при использовании ВМ с одновременной передачей информации.
4
4 5 3
3 3
• • • 3 4
3 4 2 5
Рисунок 6.2.12. Граф-схема примера алгоритма решаемой задачи для ВС с распределённой памятью с ВМ, осуществляющие одновременно обработку и передачу информации.
Таблица 6.2.5
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
3 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
4 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
5 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
6 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
7 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
8 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
9 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
10 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
11 |
|
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
4 |
12 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
3 |
13 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
4 |
14 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
2 |
15 |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
5 |
Построение нитей осуществляется аналогично как в случае ВС с общей памятью. Вычисляются ранние сроки окончания выполнения операторов, затем строится их диаграмма, как показано на рисунке 6.2.13, на основании матрицы следования (таблица 6.2.5). Ранние сроки равны соответственно: t1,1=4, t1,2 =8, t1,3 =9, t1,4 =7, t1,5 =11, t1,6=11, t1,7 =11, t1,8 =11, t1,9 =11, t1,10 =11, t1,11 =13, t1,12 =16, t1,13 =17, t1,14 =15, t1,15 =18.
-
9
8
7
9
6
8
5
7
4
6
15
3
4
5
14
2
3
11
13
1
1
2
10
12
Рисунок 6.2.13. Диаграмма ранних сроков окончания выполнения операторов для граф-схемы 6.2.12 с учётом времён передачи информации между операторами в режиме совмещения с обработкой
Для реализации граф-схемы, представленной на рисунке 6.2.12, как следует из диаграммы рисунка 6.2.13, требуется семь процессоров (ВМ). Диаграмма получилась достаточно компактной, так как отсутствуют многочисленные задержки, связанные с передачей информации.
Так как структура ВС регулярна, то в матрице дистанций, представленной в таблице 6.2.6, анализ на оптимальное размещение нитей не требуется. Для реализации цикла (нити 2, 5, 6, 7, 8, 9, 10) используем ВМ, отстоящие на дистанции 1 от нулевого ВМ. Реализовать решение заданной задачи на структуре ВС типа циркулянта (12, 1, 5), у которого не достаточно ВМ, имеющих неединичную дистанцию, проблематично, так как использование дистанции 2 требует дополнительные транзитные процессоры, которых в данной структуре недостаточно. В данном случае можно пойти двумя способами. Первый способ заключается в том, при заданном количестве ВМ увеличить количество связей. Второй – заключается в увеличении количества процессоров. Рассматривается ВС типа циркулянта (11, 1, 2. 5). Матрица дистанций для этой структуры представляется таблицей 6.2.6.
Таблица 6.2.6.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
0 |
+. |
1 |
1 |
2 |
2 |
1 |
1 |
2 |
2 |
1 |
1 |
1 |
1 |
4.6. |
1 |
1 |
2 |
2 |
1 |
1 |
2 |
2 |
1 |
2 |
1 |
1 |
7. |
1 |
1 |
2 |
2 |
1 |
1 |
2 |
2 |
3 |
2 |
1 |
1 |
12. |
1 |
1 |
2 |
2 |
1 |
1 |
2 |
4 |
2 |
2 |
1 |
1 |
0 |
1 |
1 |
2 |
2 |
1 |
1 |
5 |
1 |
2 |
2 |
1 |
1 |
8. |
1 |
1 |
2 |
2 |
1 |
6 |
1 |
1 |
2 |
2 |
1 |
1 |
9. |
1 |
1 |
2 |
2 |
7 |
2 |
1 |
1 |
2 |
2 |
1 |
1 |
15. |
1 |
1 |
2 |
8 |
2 |
2 |
1 |
1 |
2 |
2 |
1 |
1 |
0 |
1 |
1 |
9 |
1 |
2 |
2 |
1 |
1 |
2 |
2 |
1 |
1 |
10. |
1 |
10 |
1 |
1 |
2 |
2 |
1 |
1 |
2 |
2 |
1 |
1 |
3. |
Вначале размещаются нити цикла алгоритма Т2 – Т10. Затем делается попытка разместить все остальные нити. На отметке времени t=4 осуществляется обмен данными между нитями Т1 и Т3,Т4. Вначале осуществляется обмен межу нулевым ВМ и первым ВМ и нулевым ВМ и десятым. Нить 9 подключается к 6-му процессору. Размещение нитей на вычислительных модулях ВС показаны в таблице 6.2.6. На главной диагонали записываются номера нитей, отмеченных точкой. Номер строки или столбца определяет номер используемого ВМ. Покажем размещение нитей рисунка 6.2.13 на ВС типа циркулянта (11, 1, 2, 5), показанной на рисунке 6.2.14. Размещение загруженных ВМ показано в виде закрашенных вершин граф-схемы.
Рисунок 6.2.14. Загрузка циркулянта (11, 1, 2, 5) нитями граф-схемы 6.2.8