6.1.3. Вопросы к разделу 6.1
1. Определите соотношения, задающие последовательность следования в граф-схеме алгоритма.
2. В каких пределах изменяется время выполнения оператора?
3. В каких случаях может наступить равенство ранних и поздних сроков окончания выполнения операторов?
4. На чём основано утверждение леммы 6.1.1?
5. Как связаны точки SR-мерного многоугольника МТ с точками интервала [a, b]?
6. Объясните, почему на интервале [0, 1] рисунка 6.1.3 минимальная загрузка равна 0.
7. Объясните, в каких ситуациях используется теорема 6.1.2.
8. Почему важен порядок следования интервалов при выполнении алгоритма 6.1.5.
9. Не является ли Ткр нижней оценкой минимального времени выполнения данного алгоритма
10. Согласно теореме 6.1.2 всегда ли можно найти величину g, удовлетворяющую поставленным условиям?
15.Чем вызвана необходимость коррекции поздних сроков окончания выполнения операторов в алгоритме 6.1.5 шага 5?
12. Объясните, почему при выборе последовательности отрезков, как в алгоритме 6.1.4 пункте 2, значение T можно увеличивать, не пересчитывая при этом ранее вычисленные поздние сроки окончания выполнения операторов?
13. Как можно дополнить алгоритм 6.1.5, если Ткр по определённым причинам нельзя определить?
14. Чем объясняется выбор интервалов для определения минимальной загрузки вносимой оператором, который случайным образом ложится на рассматриваемый интервал?
6.2.1. Распределение операторов по вм вычислительной системы с общим полем памяти для информационной граф-схемы
Построенные диаграммы (см. рисунок 6.1.2.) является удобным средством построения плана распределения операторов по ВМ вычислительной системы. Строки временной диаграммы будем интерпретировать как нити алгоритма решаемой задачи, в соответствии с установившейся терминологией. Для удобства размещения операторов алгоритма на вычислительные модули ВС, представим структуру ВС в виде матрицы дистанций между вычислительными модулями ВС, в которой указаны расстояния между ВМ, измеренные в количестве ВМ между двумя рассматриваемыми. В качестве примера возьмём обобщённый 3-х мерного гиперкуба 2х3х3, представленный на рисунке 6.2.1.
Рисунок 6.2.1. Схема представления обобщенного 3-х мерного гиперкуба 2х3х3
Построим для него матрицу дистанций, которую, в дальнейшем удобно использовать для размещения нитей решаемой задачи. Нумерация ВМ производится, как показано в таблице 6.2.1.
Матрица дистанций представлена в таблице 6.2.2. В последней строке приведены итоговые суммы по столбцам. Минимальная сумма определяет лучший ВМ, который имеет минимальное расстояние ко всем остальным ВМ. В данном случае лучшими ВМ являются вычислительные модули с номерами 9 и 11.
Рассмотрим алгоритм, представленный граф-схемой на рисунке 6.2.2.
3 5
4 6 7 9
5 5 ••• 5 3
6 3 3 3 3
3 4 7 8 5
Рисунок 6.2.2. Граф-схема примера алгоритма решаемой задачи. Вершины 7, …, 16 представляют ветви цикла. Вершина 19, …, 22 отображает так же распараллеленный цикл
Для построения нитей решаемой задачи построим диаграмму ранних сроков окончания выполнения операторов. Используя алгоритм 6.1.1, вычислим t1,1, …, t1,27. Вычисленные данные представлены в таблице 6.2.3. Диаграмма ранних сроков окончания выполнения операторов представлена на рисунке 6.2.3.
Tак как рассматривается ВС с общей памятью, обмена данными через каналы связи между процессорами нет, и количество нитей меньше, чем число процессоров, поэтому распределение нитей между ВМ может осуществляться, например, следующим образом: первая нить загружается в первый ВМ, вторая – во второй и т. д. Процессоры с шестого по тринадцатый освобождаются в момент относительного времени Т=18 и могут быть распределены для решения других задач. Аналогично процессоры 6,7,8,9,10,11,12 также могут быть использованы другими задачами по мере их освобождения, что наглядно видно из рисунка 6.2.3.
Таблица 6.2.1
-
Кордината ВМ(х, у, z)
000
100
010
020
110
120
001
101
011
Номер ВМ
1
2
3
4
5
6
7
8
9
Кордината ВМ(х, у, z)
021
111
121
002
102
012
022
112
122
Номер ВМ
10
11
12
13
14
15
16
17
18
Построим нити для диаграммы, представленной на рисунке 6.2.2. Первую нить составят операторы: Н1={1, 3, 7, 18, 24}, H2={2, 8, 19, 23}, H3={9, 20, 26}, H4={10, 21, 25}, H5={11, 22, 25}, H6={12}, H6={12}, H7={13}, H8={14}, H9={15}, H10={16}, H11={4}, H12={5}, H13={6,14}.
Таблица 6.2.2
-
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
0
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
0
1
1
2
2
3
1
2
2
3
3
4
2
3
3
4
4
2
3
1
0
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
0
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
0
1
1
2
2
3
1
2
2
3
10
3
4
2
1
3
2
2
3
1
0
2
1
3
4
2
1
3
2
11
3
2
2
3
1
2
2
1
1
2
0
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
0
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.3
-
t1,1
t1,2
t1,3
t1,4
t1,5
t1,6
t1,7
t1,8
t1,9
t1,10
t1,11
t1,12
t1,13
t1,14
5
7
11
12
14
12
12
12
12
12
12
12
12
t1,15
t1,16
t1,17
t1,18
t1,19
t1,20
t1,21
t1,22
t1,23
t1,24
t1,25
t1,26
t1,27
12
12
14
18
17
17
17
17
21
22
24
25
22
Н
омера
вычислтельных модулей
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
22 |
|
27 |
|
|
|
|
|
|
|
|
|||
4 |
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
2
|
|
25 |
|
|
|
|
|
|
|
|
|||
3 |
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
2 |
|
26 |
|
|
|
|
|
|
|
|
||
2 |
2 |
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
1 |
2
|
|
|
|
|
|
|
|
|
||
|
1 |
|
|
3 |
|
|
|
7 |
|
|
|
|
18 |
|
|
|
|
23 |
|
|
|
|
|
|
|
|
|
||
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 |
26 |
27 |
28 |
29 |
1
0
9
4
1
Относительное время
Рисунок 6.2.3. Диаграмма ранних сроков окончания выполнения операторов
Паузы, возникшие на 6, 7, 12, 13 моментах времени связаны с синхронизацией вычислений, определяемой структурой рассматриваемой граф-схемы. Общее время решения этой задачи составляет 28 условных единиц.
Анализируя представленный способ построения плана решения задач на ВС, можно сделать вывод, что достаточно простыми средствами можно построить достаточно эффективную процедуру организации решения параллельных задач на ВС.