Графовые модели программы. Алгоритм оптимизации информационного графа по ширине пи высоте. Лекция 4

Август 3, 2022

Главная
Информатика
Графовые модели программы. Алгоритм оптимизации информационного графа по ширине пи высоте. Лекция 4

Содержание

2. Разнообразие способов решения одной задачи Пример: увеличение i-го среза трехмерной матрицы А на величину двухмерной матрицы
3. Способ 1 организации суммирования
4. Способ 2 организации суммирования
5. Пример 2 Умножение матриц 1. Возможен ли другой порядок? 2. Нужен ли другой порядок?
6. Отношение скоростей умножения матриц
7. Система функциональных устройств (ФУ) Определение. Информационная структура программы. Подходы к исследованию информационной структуры программы Денотационный Операционный
8. Операционная связь Дуги: операционная связь Две вершины A и B соединяются направленной дугой тогда и только
9. Информационная связь Дуги: информационная связь Две вершины A и B соединяются направленной дугой B тогда и
10. Пример: Система линейных уравнений Дано: СЛАУ: Ax=b; A(nxn) – левая двухдиагональная матрица; ai – диагональные элементы,
11. Граф управления Алгоритм: y=b1/a1; x=y; for (i=1; i x = (bi-cix)/ai; if (x y=x; } Дано:
12. Граф операционно-логической истории Дано: Начальные данные; Последовательный вычислитель; Вершины графа – каждое срабатывание каждой операции: П
13. Информационный граф Дано: Вершины графа – преобразователи: П; Ребра графа – возможные срабатывания П друг за
14. Граф истории реализации программы Дано: Начальные данные; Последовательный вычислитель; Вершины графа – каждое срабатывание каждого преобразователя:
15. 4 графовые модели Граф управления; Граф операционно-логической истории; Информационный граф; Граф истории реализации.
16. Дополнительные вопросы 1. Может ли граф истории реализации некоторого фрагмента программы иметь 100 вершин и ни
17. Дополнительные вопросы 3. Может ли граф истории реализации некоторого фрагмента программы иметь 20 вершин и 200
18. Дополнительные вопросы 4. Модель некоторого фрагмента программы в качестве подграфа содержит следующий граф: Какой моделью могла
19. Множество графовых моделей программ Граф управления Граф операционно-логической истории Информационный граф Граф истории реализации Операционные модели
20. Информационная структура
21. Модель вычислений в виде информационного графа алгоритма Граф алгоритма – это граф истории реализации алгоритма. Свойства:
22. Детерминированные и недетерминированные алгоритмы Классификация по «IF» Детерминированный Недетерминированный + - 1. Взаимно-однозначное соответствие между операциями
23. Параллельная форма графа Утверждение 1. Пусть граф алгоритма имеет n – вершин. Тогда ∃ число s
24. Параллельная форма графа n = 14 s = 9 Результат.
25. Параллельная форма графа - начальная вершина каждой дуги расположена на ярусе с номером меньшим, чем номер
26. Параллельные формы графа Параллельные формы графа Строгая (i Обобщенная (i Каноническая (все входные вершины на 1-м
27. Какие это параллельные формы графа?
28. Ускорение по Амдалу
29. Виды параллелизма Параллелизм Конечный Массовый Конечный параллелизм определяется информационной независимостью некоторых фрагментов в тексте программы. Массовый
30. Пример. Произведение элементов вектора. Схема последовательного умножения:
31. Процесс сдваивания Схема последовательного умножения: Процесс сдваивания
32. Модели параллельных вычислений В теории – идея неограниченного параллелизма: Оптимальное решение: минимальная ширина при минимальной высоте.
33. Параллельная форма графа Высота графа: h = 9; Ширина графа: d = 3; Число вершин: n=14;
34. Модели параллельных вычислений Минимальное количество необходимых процессоров = ширина графа: В этом случае: Плотность вычислений: Ускорение:
35. Часть 1. Определение групп вершин графа и минимальных высоты и ширины (приведение к параллельной форме)
36. Часть 1. Определение групп вершин графа и минимальных высоты и ширины (приведение к параллельной форме)
37. Часть 1. Определение групп вершин графа и минимальных высоты и ширины (приведение к параллельной форме) ⇒
38. Часть 1. Определение групп вершин графа и минимальных высоты и ширины (приведение к параллельной форме) ⇒
39. Часть 1. Определение групп вершин графа и минимальных высоты и ширины (приведение к параллельной форме) ⇒
40. Результаты работы алгоритма Итого 6 групп: Время выполнения: 6 Число процессов: 4
41. Оптимизация информационного графа Жесткие пузыри: 1 Всего пузырей: 8 5. Начиная с последней группы найти группу
42. Оптимизация информационного графа Ширина равна 1. Δd=d-dk=3-1=2. Добавить можем 2 элемента. M5={14}, x=14. Составляем всевозможные пары
43. Оптимизация информационного графа Ширина равна 1. Δd=d-dk=3-1=2. Добавить можем 2 элемента. M4={7, 11, 13}, x=7. Составляем
44. Оптимизация информационного графа Ширина равна 1. Δd=d-dk=3-1=2. Добавить можем 2 элемента. M3={15, 5, 10, 12}, x=15.
45. Оптимизация информационного графа M5={14,11,13} M4={7,5,15} M3={10,12,2} M2={4,6,9} M1={1,3,8}
46. Результат оптимизация информационного графа Жесткие пузыри: 1 Всего пузырей: 8 Число процессов: 4 Время: 6 Жесткие
47. Оценка минимальной ширины графа с учетом числа групп: di - ширина i-й группы, m – число
48. Оценка минимальной ширины графа с учетом числа групп: di - ширина i-й группы, m – число
50. Скачать презентацию

Слайд 2

Разнообразие способов решения одной задачи
Пример: увеличение i-го среза трехмерной матрицы А

на величину
двухмерной матрицы В и сумму элементов предыдущих срезов:

Слайд 3

Способ 1 организации суммирования

Слайд 4

Способ 2 организации суммирования

Слайд 5

Пример 2 Умножение матриц
1. Возможен ли другой порядок?
2. Нужен ли другой

порядок?

Слайд 6

Отношение скоростей умножения матриц

Слайд 7

Система функциональных устройств (ФУ)
Определение. Информационная структура программы.
Подходы к исследованию
информационной структуры

программы

Денотационный

Операционный

Операционный подход

Основа. Графовые модели.

Объекты. Действия и связи.

Действия: преобразователи – П;
распознаватели – Р.

Связи

Операционная связь
(связь по управлению)

Информационная
связь

Вершины: процедуры, циклы, линейные участки, операторы, итерации циклов, срабатывания операторов…

Дуги: отражают связь между вершинами.

Слайд 8

Операционная связь
Дуги: операционная связь
Две вершины A и B соединяются направленной дугой

тогда и только тогда, когда вершина B может быть выполнена сразу после вершины A.

Операционная связь= связь по передаче управления.

x(i) = a + b(i) (1)
y(i) = 2*x(i) – 3 (2)
t1 = y(i)*y(i) + 1 (3)
t2 = b(i) – y(i)*a (4)

Пример:

Слайд 9

Информационная связь
Дуги: информационная связь
Две вершины A и B соединяются направленной дугой

B тогда и только тогда, когда вершина использует в качестве аргумента некоторое значение, полученное в вершине A.

Информационная связь= связь по передаче данных.

x(i) = a + b(i) (1)
y(i) = 2*x(i) – 3 (2)
t1 = y(i)*y(i) + 1 (3)
t2 = b(i) – y(i)*a (4)

Пример:

Слайд 10

Пример: Система линейных уравнений
Дано:
СЛАУ: Ax=b;
A(nxn) – левая двухдиагональная матрица;
ai – диагональные

элементы, i=1..n;
ci – поддиагональные элементы, i=1..n, c1 = 0;
bi – правые части, i=1..n;
xi – координаты решения, i=1..n.
Найти:
максимальную координату вектора-решения.

Алгоритм:
y=b1/a1;
x=y;
for (i=1; i<=n; i++) {
x = (bi-ci*x)/ai;
if (x<=y) break;
y=x;
}

Преобразователи: 1, 2, 4, 6.
Распознаватели: 3, 5, 7.

Слайд 11

Граф управления
Алгоритм:
y=b1/a1;
x=y;
for (i=1; i<=n; i++) {
x = (bi-cix)/ai;
if (x<=y)

break;
y=x;
}

Дано:
Вершины графа – все операции: П ∪ Р;
Ребра графа – возможные срабатывания операций друг за другом.

for( i = 0; i < n; ++i) {
A[i] = A[i – 1] + 2;
B[i] = B[i] + A[i];
}

Граф управления не зависит
от входных данных.

Слайд 12

Граф операционно-логической истории
Дано:
Начальные данные;
Последовательный вычислитель;
Вершины графа – каждое срабатывание каждой операции:

П ∪ Р;
Ребра графа – непосредственные срабатывания операций друг за другом.

Граф операционно-логической истории – единственный путь от начальной вершины к конечной.

Пример 1:

Алгоритм:
y=b1/a1;
x=y;
for (i=1; i<=n; i++) {
x = (bi-cix)/ai;
if (x<=y) break;
y=x;
}

Пример 2:

Слайд 13

Информационный граф
Дано:
Вершины графа – преобразователи: П;
Ребра графа – возможные срабатывания П

друг за другом.

Алгоритм:
y=b1/a1;
x=y;
for (i=1; i<=n; i++) {
x = (bi-cix)/ai;
if (x<=y) break;
y=x;
}

Информационный граф не зависит от входных данных.

Граф зависимостей

Слайд 14

Граф истории реализации программы
Дано:
Начальные данные;
Последовательный вычислитель;
Вершины графа – каждое срабатывание каждого

преобразователя: П;
Ребра графа – непосредственные срабатывания П друг за другом.

Пример 1:

Алгоритм:
y=b1/a1;
x=y;
for (i=1; i<=n; i++) {
x = (bi-cix)/ai;
if (x<=y) break;
y=x;
}

Пример 2:

Слайд 15

4 графовые модели
Граф управления;
Граф операционно-логической истории;
Информационный граф;
Граф истории реализации.

Слайд 16

Дополнительные вопросы
1. Может ли граф истории реализации некоторого фрагмента программы иметь

100 вершин и ни одной дуги?

ДА

2. Может ли граф истории реализации некоторого фрагмента программы иметь 67 вершин и 3 дуги?

ДА

Слайд 17

Дополнительные вопросы
3. Может ли граф истории реализации некоторого фрагмента программы иметь

20 вершин и 200 дуг??

НЕТ

Свойства графа истории реализации:
ациклический граф;
нет кратных дуг.

Макс.число дуг: (n-1) + (n-2) + (n-3) + … + 2 + 1 = n*(n-1)/2

Если n=20, то макс.число дуг = 20*(20-1)/2=190

Слайд 18

Дополнительные вопросы
4. Модель некоторого фрагмента программы в качестве подграфа содержит следующий

граф:

Какой моделью могла бы быть исходная модель?
ГУ ИГ ОЛИ ИР

Слайд 19

Множество графовых моделей программ
Граф управления
Граф операционно-логической истории
Информационный граф
Граф истории реализации
Операционные
модели
Истории
Компактные

модели

Информационные
модели

Слайд 20

Информационная структура

Слайд 21

Модель вычислений в виде информационного графа алгоритма
Граф алгоритма – это граф

истории реализации алгоритма.

Свойства:
Связный граф;
Ориентированный граф;
Ацикличный граф;
Мультиграф;
Может быть взвешенным.

Определения:
Входные вершины;
Выходные вершины.

Пример:

Слайд 22

Детерминированные и недетерминированные алгоритмы
Классификация по «IF»
Детерминированный
Недетерминированный
+
-
1. Взаимно-однозначное соответствие между операциями

-> проще устроены;
2. Широкий класс задач;
3. ∀ недетерминированный алгоритм можно свести к детерминированному:
- путем укрупнения;
- путем декомпозиции.

Причины исследования детерминированных алгоритмов:

Алгоритм:
x=b1/a1;
y=b2/a2;
z=b3/a3;
if (x<=y) x = (b1-c1*x)
else x=(b1+c1*x);
if (y<=z) y = (b2-c2*y)
else y=(b2+c2*y);
f=x+y+z;

Алгоритм:
x=b1/a1;
y=b2/a2;
z=b3/a3;
A(x,y);
B(y,z);
f=x+y+z;

A(x,y)

B(y,z)

Слайд 23

Параллельная форма графа
Утверждение 1.
Пусть граф алгоритма имеет n – вершин. Тогда

∃ число s ≤ n, для которого все вершины графа можно так пометить одним из индексов 1, 2, …, s, что если ∃ дуга (i, j), то i < j.

Доказательство.

n = 14

13’

1’

2’

3’

4’

5’

6’

7’

8’

9’

10’

11’

12’

14’

Слайд 24

Параллельная форма графа
n = 14
s = 9
Результат.

Слайд 25

Параллельная форма графа
- начальная вершина каждой дуги расположена на ярусе с

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

Высота графа – это число ярусов;
Ширина яруса – число вершин, расположенных на ярусе;
Ширина графа – это максимальная ширина ярусов в графе.
Высота графа = сложность параллельной реализации алгоритма/программы.

Слайд 26

Параллельные формы графа
Параллельные формы графа
Строгая (i < j);
Обобщенная (i <=

j);
Каноническая (все входные вершины на 1-м ярусе);
Максимальная (минимальная высота).

Высота графа: h = 9;
Ширина графа: d = 3;
Число вершин: n=14;
Число ребер: r = 15;

Ширина графа

Высота графа

взаимоисключающие

Максимальная форма
всегда является
канонической

Слайд 27

Какие это параллельные формы графа?

Слайд 28

Ускорение по Амдалу

Слайд 29

Виды параллелизма
Параллелизм
Конечный
Массовый
Конечный параллелизм определяется информационной независимостью некоторых фрагментов в тексте программы.
Массовый

параллелизм определяется информационной независимостью итераций циклов программы.

Пусть:
Время операции = 1;
Время передачи данных = 0;
Число процессоров = ∝;
Память общая.
Результат:
Концепция неограниченного параллелизма =
построение алгоритма минимальной высоты

Слайд 30

Пример. Произведение элементов вектора.

Схема последовательного умножения:

Слайд 31

Процесс сдваивания
Схема последовательного умножения:

Процесс сдваивания

Слайд 32

Модели параллельных вычислений
В теории – идея неограниченного параллелизма:
Оптимальное решение: минимальная

ширина при минимальной высоте.

На практике – определенное количество процессоров:

Без учета передачи данных

С учетом передачи данных

Слайд 33

Параллельная форма графа
Высота графа: h = 9;
Ширина графа: d = 3;
Число

вершин: n=14;
Число ребер: r = 15;

Ширина графа

Высота графа

Слайд 34

Модели параллельных вычислений
Минимальное количество необходимых процессоров = ширина графа:
В

этом случае:
Плотность вычислений:

Ускорение:

Эффективность:

Пусть: Ni – число процессоров на i-м ярусе
N = max(Ni) – общее число задействованных процессоров

Слайд 35