поскольку операция композиции 0 ассоциативна. Наша цель - вычислить все у; = [0, г].

Схема состоит из одинаковых элементов, каждый из которых вычисляет композицию <g>. Идея её проста: на первом уровне параллельно вычисляются композиции пар ([1, 2], [3,4],...), затем четвёрок и так далее, пока мы не дойдем до композиции всех элементов. Затем мы движемся в обратном направлении, пока не доходим до искомых уг-. Фрагмент дерева (внутренняя вершина и её потомки) показан на рис. 29.8. На рис. 29.9 показана полная схема для га = 8. Входы х\,.. .хп и выходы уо,... , Уп-i расположены в листьях дерева, а вход жо и выход уп - в корне, так что данные движутся по дереву сначала от листьев к корню, а потом обратно.

Рис. 29.8 Схема для параллельного вычисления префиксов. Показана внутренняя вершина, отвечающая за х, . . .Хк- Левое поддерево объединяет входы Xi,... ,xj - i, правое - входы х3,... ,Хк- Два элемента Сх) (один используется при прямом ходе, другой - при обратном) вычисляют [г, к] = [г, j - 1] Сх) [j, к] и [О, J - 1] = [0, г - 1] СХ) [г, J - 1].

Рис. 29.9 29.9 Случай п = 8. (а) Общая структура и вычисляемые значения (Ь) Значения, соответствующие примеру на рис. 29.3

Два элемента <g> в каждом узле работают в разное время (имеют разную глубину): левый (на рис. 29.8) работает «на пути вверх», а правый - на пути вниз. Убедиться в том, что схема работает правильно, можно по индукции. Предполагая, что поддеревья на рис. 28.8 вычисляют [i,j - 1] и [j,k], мы получаем, что левый элемент <g> вычисляет [г, /г]так что вычисления снизу вверх правильны. Проследим за движением информации вниз. Предполагая, что в вершину на рис. 29.8 сверху приходит правильное значение [О, г - 1], мы видим, что правый элемент <g> правильно вычисляет [0,j - 1] = [0, г - 1] (g) [i,j - 1]. Это значение передаётся правому сыну; левому передаётся неизменённое значение [0, г - 1].

Строение корня дерева (дополнительный элемент <g>) показано на рис. 29.9.

Если п является степенью двойки, то в параллельной префиксной схеме 2га - 1 элемент. Время работы составляет O(lgra), поскольку дерево имеет высоту lg га, а данные проходят по нему дважды (вверх и вниз).

29.2.4. Сумматор с предвычислением переносов: окончание

Полная конструкция га-разрядного сумматора с предвычислением переносов (carry-lookahead adder) показана на рис. 29.10. Кро-

Рис. 29.10 29.10 Сумматор с предвычислением переносов (показан случай п = 8) состоит из п + 1 блока KPG с номерами от 0 до п. Блок KPG, получает на вход а, и bi, вычисляет тип переноса х, и обрабатывает выходное значение у,, выдавая г-ый бит суммы s,. Показаны значения для примера рис. 29.3

ме разобранной схемы параллельного вычисления префиксов, него входит га + 1 блок KPG. Блок KPG с индексом г вычисляет по входам a,i,bi тип переноса жг- и передаёт его наверх, а затем, получив сверху значение уг- (которое, согласно лемме 29.1, соответствует биту переноса сг), вычисляет с помощью сумматора FA{ значение г-го бита суммы Si. Значения ага+1 = 0, bn+i = 0 и жо = к зафиксированы. Поскольку все операции, кроме выполняемых параллельной префиксной схемой, требуют времени 0(1), общее время работы схемы составляет О (lgra). Размер схемы равен в (га).

29.2.5. Сложение с запоминанием переносов

Как ни странно, сложение трёх чисел почти не требует дополнительных затрат по сравнению со сложением двух: глубина увеличивается всего на несколько единиц. Пусть ж = (жга 1,жга 2,... ,жо),

У = (Уп-1, Уп-2, , Уо) И Z = (zn-i,Zn-2, - ,Zq) - Три П-

разрядных числа. Схема сложения с запоминанием переносов (carry-save adder) находит два числа и = (ип 2, ип-2, ,хо) (п битов) и v = (vn, vn-i,... , vo) (га + 1 битов), для которых

uA-v = xA-yA-z.

Она делает это следующим образом (рис. 29.11 (Ь)):

щ = parity(жг-, yi, Zi),

vt+1 = majority-, уг, zt)

(для iu = 0,1,... , га - 1; бит vo всегда равен 0). Рассмотрим числа и =ип 2,... , и0) и v = (vn, ип ь ... ,v0). Легко видеть, что

xA-yA-z = uA-v

Числа и и v могут быть вычислены за время 0(1) с помощью га сумматоров FAo,... , FAn i (рис. 29.11). Для сложения чисел и и v используется сумматор с предвычислением переносов. Это требует времени О (lgra), всего получается 0(1) + О (lgra), то есть О (lgra). Хотя та же асимптотическая оценка получается при использовании двух сумматоров с предвычислением переносов, но на практике разница (примерно в два раза) существенна.

Аналогичный приём (сведение сложения трёх чисел к сложению двух) играет важную роль в быстрых схемах для умножения (см. раздел 29.3).

Рис. 29.11 (а). Схема сложения с запоминанием переносов. Для сложения трёх n-битовых чисел x,y,z вычисляются числа и (п битов) и v (п + 1 битов), для которых x-\-y-\-z = u-\-v. (b) 8-разрядный сумматор с запоминанием переносов. Каждый из сумматоров FA, получает на вход x,,y,,z, и выдаёт бит суммы и, и бит переноса v,. Мы полагаем vo = 0.

Упражнения

29.2-1 Пусть га = 8, а = (01111111), Ь = (00000001). Укажите биты переноса и типы переноса во всех разрядах, а также значения на всех проводах схемы рис. 29.9, включая выходы уо,у\,... , у$.

29.2-2 Докажите, что операция <g> (заданная таблицей рис. 29.5) ассоциативна.

29.2-3 Объясните, как должна быть устроена параллельная префиксная схема, если га не является степенью двойки (например, рассмотрите случай га = 11). Каково время работы такой схемы?

29.2-4 Покажите внутреннее устройство схемы KPG, если значения на входах и выходах кодируются так: на входах (00) соответствует к, (11) - g, (01) или (10) - р; на выходах 0 соответствует к,

29.2-5 Укажите глубину каждого провода на рис. 29.9 (а). Найдите критический (самый длинный) путь (critical path) от входов к выходам и покажите, что его длина есть O(lgra). Найдите узел, два элемента <g> которого срабатывают с интервалом О (lgra). Есть ли узлы, в котором два элемента <g> срабатывают одновременно?

29.2-6 Следую образцу рис. 29.12, укажите способ построения схемы вычисления префиксов для любого числа входов, являющегося степенью двойки. Докажите, что схема имеет глубину ©(lg га) и размер О (га lgra). Докажите, что схема работает правильно, разбив её на блоки и рассуждая индуктивно.

Рис. 29.12 29.12 Параллельная префиксная схема для упражнения 29.2-6

29.2-7 Какова максимальная выходная степень каждого провода в схеме с предвычислением переносов? Постройте схему для сложения глубины О (lgra) и размера О (га), в которой все провода имеют выходную степень 0(1).

29.2-8 Постройте счётчик единиц - схему с га входами и [~lg(ra + 1)] выходами, выдающую число единиц среди входов, записанное в двоичной системе. (Например, вход (10011110) порождает выход (101) (пять единиц). Глубина схемы должна составлять О (lg га), размер - ©(га).

29.2-9* Постройте схему для сложения глубины 4 и полиномиально зависящего от га размера, используя элементы AND и OR с произвольным числом входов. (Дополнительный вопрос: сделайте то же самое для глубины 3.)

29.2-10* Пусть на каждом входе каскадного суматора га-