Составители:
Рубрика:
Д о к а з а т е л ь с т в о. Используя сведения об имеющихся
функциональных устройствах, укажем в вершинах графа время
выполнения соответствующих операций. Далее заменим все вер-
шины графа линейными цепочками новых вершин, число которых
совпадает со временем выполнения упомянутых операций и постро-
им для полученного графа его каноническую максимальную парал-
лельную форму
*
. Очевидно, что высота этой формы равна макси-
мальному из врем¨ен последовательного выполнения всех операций,
находящихся на различных путях исходного графа (т.е. высота на
единицу больше длины критического пути графа). На месте каждо-
го яруса поставим соответствующее конвейерное функциональное
устройство. Ясно, что в результате получится набор функциональ-
ных устройств, позволяющий реализовывать алгоритм за указанное
в утверждении время. Теорема доказана.
Замечание. На каждом ярусе вместо конвейерных функцио-
нальных устройств можно использовать простые функциональные
устройства, но в значительно большем количестве (примерно во
столько раз больше, во сколько больше длительность выполнения
операций). Нетрудно видеть, что хотя общее время решения задачи
может уменьшаться при использовании б´ольшего количества функ-
циональных устройств, но тем не менее при заданном наборе типов
функциональных устройств оно ограничено снизу, так что начиная
с некоторого момента дальнейшее увеличение количества функци-
ональных устройств бесполезно; при этом, как правило, не реали-
зуется полная загруженность системы ни при каком наборе функ-
циональных устройств.
Постоянно возникают следующие кардинальные вопросы:
– нужно ли создавать специализированные параллельные си-
стемы для решения тех или иных классов задач (для некоторых
таких классов ответ оказывается отрицательным),
– что следует делать для увеличения загруженности системы,
– как заранее распознавать трудные для распараллеливания
ситуации.
Ответы на подобные вопросы можно получить лишь при рас-
смотрении конкретных ситуаций.
*
Параллельная форма называется канонической, если она — результат то-
пологической сортировки графа; в этом случае все пути начинаются на первом
ярусе.
61
Страницы
- « первая
- ‹ предыдущая
- …
- 58
- 59
- 60
- 61
- 62
- …
- следующая ›
- последняя »
