Составители:
Рубрика:
2) провести одно параллельное деление для вычисления част-
ных
e
ikπ/n
x − e
ikπ/n
, k = 1, . . . , n,
3) найти сумму n слагаемых по схеме сдваивания за dlog
2
ne
параллельных сложений,
4) сделать одно деление: делим n на полученную только что
сумму,
5) добавить единицу.
В результате оказывается, что выражение x
n
можно вычис-
лить, используя 2 параллельные мультипликативные операции и
dlog
2
ne + 2 параллельных аддитивных операций.
Замечание. В приведенном примере предполагается, что чис-
ла e
ikπ/n
, k = 1, 2, . . . , n подсчитаны заранее и запасены в вычисли-
тельной системе (это — естественное предположение при возведе-
нии большого количества чисел x в одну и ту же степень n). Если
предположить, что сложение выполняется быстрее умножения, и не
принимать в расчет другие аспекты реализации, то можно считать,
что предлагаемый в 1) – 5) алгоритм вычисления x
n
эффективнее
схемы сдваивания при умножении.
§ 10. О взаимоотношении числа данных
и высоты параллельной формы
Схему сдваивания можно сформулировать в более общей фор-
ме. Рассмотрим множество M с ассоциативной бинарной опера-
цией ∗; пусть в этом множестве имеется единица, т.е. такой эле-
мент e, что для любого элемента a из M выполняется соотношение
e∗a = a∗e = a . Множество M называют ассоциативным моноидом,
а операцию ∗ — умножением в M.
Будем считать, что рассматриваемая бинарная операция отно-
сится к числу основных операций (см.§ 7). Справедливо следующее
утверждение.
Теорема 10.1. Если требуемый результат может быть получен
из n данных последовательным применением бинарной операции ∗
в ассоциативном моноиде M, то в условиях неограниченного па-
раллелизма высота h параллельной формы, получаемой по схеме
сдваивания, дается соотношением h = dlog
2
ne.
Д о к а з а т е л ь с т в о аналогично доказательству теоремы 1.
25
Страницы
- « первая
- ‹ предыдущая
- …
- 22
- 23
- 24
- 25
- 26
- …
- следующая ›
- последняя »
