Составители:
Рубрика:
минимальное для данной системы время, то хотя бы одна строка
векторного неравенства (2.1) обращается в точное равенство.
Д о к а з а т е л ь с т в о. От противного. Если все строки в (2.1)
являются строгими неравенствами, то это означает, что каждый ре-
зультат выполнения операций записывается в память. В этом слу-
чае очевидно, что время выполнения алгоритма можно уменьшить,
если начинать выполнение операций сразу после получения послед-
него аргумента.
Следствие 2.1. Если при временной развертке t алгоритм
реализуется за минимально возможное время, то обращаются в
равенства те строки неравенства (2.1), которые соответствуют
дугам критических путей графа алгоритма с матрицей инциден-
ций A.
Замечание. Обращение какой-либо строки (2.1) в равенство
говорит о том, что для соответствующей пары операций результат
выполнения одной из них сразу же используется как аргумент для
другой. Если все строки (2.1) представляют собой равенства, то это
означает, что при реализации алгоритма не используется память
для хранения результатов промежуточных вычислений.
Теорема 2.3. Для того чтобы при реализации на вычисли-
тельной системе данного алгоритма не использовалась память
для хранения промежуточных результатов, необходимо и доста-
точно, чтобы вектор t временной развертки удовлетворял равен-
ству
−A
T
t = h (2.5)
и ограничениям, накладываемым вычислительной системой.
Следствие 2.2. В условиях выполнения равенства (2.5) алго-
ритм реализуется за минимально возможное время при заданных
длительностях выполнения операций.
Из предыдущего видно, что исследование реализаций алгорит-
ма, наилучших с точки зрения быстродействия и к тому же не тре-
бующих памяти для хранения результатов промежуточных вычис-
лений, связано с исследованием множества решений системы (2.5).
Критерий существования упомянутых реализаций — разрешимость
системы (2.5) на множестве временных разверток, удовлетворяю-
щих ограничениям вычислительной системы.
Как известно, для существования хотя бы одного решения си-
стемы (2.5) на множестве всех векторов t с вещественными ком-
понентами, необходимо и достаточно, чтобы правая часть h была
88
Страницы
- « первая
- ‹ предыдущая
- …
- 85
- 86
- 87
- 88
- 89
- …
- следующая ›
- последняя »
