Математическое моделирование на графах. Часть 1. Берцун В.Н. - 40 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

40 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
операций, соответствующих данной вершине графа). Дугами будем
изображать каналы обмена данными. Каждой дуге можно поставить
в соответствие время пересылки и пересылаемую переменную. Если
(в соответствии с алгоритмом) операция u поставляет аргумент для
выполнения операции v, то u соединяется дугой с вершиной v. Когда
результат выполнения одной операции используется в N других опе-
рациях, то из соответствующей вершины выходит N дуг. Если аргу-
ментами являются входные данные, то соответствующие дуги графа
могут отсутствовать. Так как в топологической сортировке никакие
две вершины с одним индексом не связаны дугой, то их можно ото-
ждествить с ярусом ПФА, а число вершин с одним индексом с ши-
риной яруса. Таким образом, если граф описывает некоторый алго-
ритм, то множество параллельных форм алгоритма определяется ко-
личеством его топологических сортировок. Например, на рис. 1.44
приведены две топологические сортировки одного и того же алго-
ритма вычисления суммы
12 8
Sa a a=+ ++…
с помощью алгоритма попарного суммирования (алгоритма сдваи-
вания). Здесь в качестве начальных вершин выбраны начальные
данные
,1,8.
i
ai=
1
2
3
0
4
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
Рис. 1.44
Таким образом, зная параллельные формы алгоритма, можно вы-
брать наиболее оптимальную из них для реализации на конкретной
МВС. На выбор оптимальных ПФА влияет и структура вычисли-

Страницы