Составители:
Рубрика:
Д о к а з а т е л ь с т в о. Сначала зафиксируем i ∈ {1, 2, . . . , s} и
рассмотрим формулу
X
i
= A
i1
X
i−1
+ A
i2
X
i−2
+ . . . + A
ir
X
i−r
+ B
i
(4.4)
Здесь X
i−1
, . . . , X
i−r
уже известны.
Для вычисления каждого произведения A
ij
X
i−j
согласно тео-
реме 1 можно построить параллельную форму с высотой dlog
2
ne+1
и шириной n
2
. Поскольку все упомянутые произведения (для j =
1, 2, . . . , r ) можно вычислять параллельно, то достаточно лишь уве-
личить ширину параллельной формы в r раз, сохранив прежнюю
высоту; поэтому указанные вычисления можно осуществить с по-
мощью параллельной формы высоты dlog
2
ne + 1 и ширины n
2
r.
Для вычисления (4.4) осталось провести r сложений векторов; это
можно делать параллельно для всех векторных компонент, исполь-
зуя алгоритм сдваивания, что потребует применить параллельную
форму высоты dlog
2
(r +1)e с шириной nd(r +1)/2e. Поскольку этот
этап вычислений лишь добавляет ярусы к параллельной форме, но
не меняет ее ширину (очевидно, nd(r + 1)/2e ≤ n
2
r) имеем на i-м
шаге алгоритма
dlog
2
ne + 1 + dlog
2
(r + 1)e
ярусов, причем ширина формы остается прежней n
2
r.
Наконец, вычисления по формуле вида (4.4) нужно повторить
s раз; поскольку здесь вычисления зависимы, то расширением фор-
мы обойтись нельзя: нужно увеличить количество ярусов в s раз.
Итак, для всей совокупности рассматриваемых вычислений по-
лучается параллельная форма высоты
s(dlog
2
ne + 1 + dlog
2
(r + 1)e)
и ширины n
2
r. Теорема доказана.
Возникает вопрос, нельзя ли построить параллельную форму
с более слабой зависимостью высоты от s. Следующее утверждение
показывает, что это возможно за счет увеличения ширины парал-
лельной формы.
Теорема 4.2 Существует параллельная форма для вычисле-
ния векторов (4.2) с высотой
h = dlog
2
(s + 1)e(dlog
2
(nr + 1)e + 1)
30
Страницы
- « первая
- ‹ предыдущая
- …
- 27
- 28
- 29
- 30
- 31
- …
- следующая ›
- последняя »
