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

UptoLike

ВУЗ: 

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

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

Рубрика: 

ния операций или являются конвейерными, называют синхронизи-
рованной.
Теорема 1.4. Любую базовую вычислительную систему
можно сделать уравновешенной с помощью добавления функцио-
нальных устройств, осуществляющих операцию задержки во вре-
мени.
Д о к а з а т е л ь с т в о. Рассмотрим каноническую параллель-
ную
форму базовой системы. Проведем индукцию по ярусам. Предпо-
ложим, что для некоторого k и любого l, 1 ≤ l ≤ k, равны суммы
времен срабатывания всех функциональных устройств, находя-
щихся на любых путях, связывающих входы базовой системы с
любым фиксированным входом функционального устройства l-го
яруса. Это очевидно для k = 1.
Предположим, что утверждение верно для некоторого k. Рас-
смотрим (k + 1)-й ярус и возьмем максимальную сумму, соответ-
ствующую (k + 1)-му ярусу. Все дуги, лежащие на путях с меньшей
суммой и ведущие с k-го яруса на (k + 1)-й, разомкнем и вста-
вим функциональное устройство задержки равной разности макси-
мальной суммы и рассматриваемой. Теперь будут равными суммы
времен срабатывания всех функциональных устройств, находящих-
ся на любых путях, связывающих входы базовой системы и входы
любого функционального устройства (k + 1)-го яруса. Теорема до-
казана.
Замечание. Вставка функционального устройства задержки
может рассматриваться как присоединение максимальной памя-
ти специального вида или как присоединение функционального
устройства, осуществляющего тождественное преобразование ин-
формации.
Определение 1.5. Пусть режим работы вычислительной
системы состоит в том, что очередное срабатывание функциональ-
ного устройства возможно, когда результат предыдущего срабаты-
вания этого функционального устройства уже использован или ис-
пользуется в момент подачи команды на срабатывание, причем са-
ми команды подаются без задержки по мере готовности аргумен-
тов. Такой режим называется режимом максимального быстро-
действия. Режим максимального быстродействия может нарушать
выполнение исходного алгоритма.
Замечание. Заставляя синхронизированную систему работать
80

Страницы