Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 72 стр.

UptoLike

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

Рубрика:

случае могут получиться петли и кратные дуги, которые, по суще-

ству, нужно будет отбросить.

Теорема 3.6. Пусть граф алгоритма связный и строго на-

правленный. Предположим, что длина проекции каждой из дуг на

направляющий вектор пропорциональна времени выполнения опе-

рации, находящейся в начале дуги, а времена выполнения опера-

ций, соответствующих вершинам с совпадающими проекциями,

одинаковы. Тогда на вычислительной системе, построенной в со-

ответствии с теоремой 3.5, можно реализовывать алгоритм за

минимально возможное время.

Д о к а з а т е л ь с т в о. Время включения каждого функцио-

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

ций, а крайние проекции соответствуют начальным и конечным

значениям времени работы системы. Очевидно, что в указанных

условиях их разность минимальна.

Рис. 11. Строго направленный граф.

Теорема 3.7. Пусть алгоритм реализуется на некоторой

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

незадействованные функциональные устройства и лишние связи,

то останется подграф, который получается из графа алгоритма

с помощью операций простого гомоморфизма.

Д о к а з а т е л ь с т в о очевидно.

Приведем пример построения графа вычислительной системы.

Рассмотрим алгоритм со строго направленным графом, изображен-