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

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

жет быть проведена определенная оптимизация.
Теорема 1.2. Пусть установлена такая функция соответ-
ствия между вершинами графа алгоритма и срабатываниями
функционального устройства, при которой алгоритм может
быть выполнен. Для того чтобы при этой функции алгоритм
выполнялся за минимальное время, достаточно, чтобы каждый
момент включения функционального устройства совпадал с мо-
ментом получения последнего аргумента выполняемой на данном
включении операции.
Д о к а з а т е л ь с т в о. Поскольку дана функция соответствия,
при которой алгоритм может быть выполнен, то следовательно за-
фиксирована некоторая параллельная форма алгоритма, ярусы ко-
торой и будем использовать в доказательстве.
Для данного функционального устройства при его первом сра-
батывании соответствующую ему вершину поместим в s-й ярус, ес-
ли в нее ведет путь максимальной длины s − 1, а при повторном
срабатывании поместим ее в ярус, номер которого не меньше номе-
ра яруса предыдущего срабатывания и больше ведущего в нее пути
максимальной длины.
Рассмотрим два режима включения функционального устрой-
ства. Пусть первый режим соответствует утверждению теоремы
(т.е. функциональное устройство включается в момент поступления
к нему всех необходимых данных), а второй режим пусть обеспечи-
вает минимальное время реализации алгоритма. Сравним оба ре-
жима по длительности. Будем считать, что у обоих режимов совпа-
дают начала работы системы функциональных устройств. Первый
режим единственный (по способу построения); поэтому все функ-
циональные устройства первого яруса включаются в один момент.
Длительность второго режима не изменится, если мы предполо-
жим, что все функциональные устройства первого яруса у него то-
же включаются в один момент. Но тогда у обоих режимов будут в
один момент включаться все устройства первых ярусов. Для вто-
рого режима устройства второго яруса не могут включаться ранее,
чем устройства второго яруса первого режима (ввиду его определе-
ния). Теперь аналогичным рассуждением приходим к выводу, что
все устройства второго яруса в обоих режимах включаются одно-
временно.
Продолжая эти рассуждения приходим к выводу, что пер-
вый режим включения функционального устройства реализует
77

Страницы