этапе параллельно работающие сумматоры требуют времени 0(1), этапов в (lgra), последнее сложение (с предвычислением переносов) тоже требует времени в (lgra), так что общее время будет в (lgra) при размере в(га2).

Дерево Уоллеса для га = 8 показано на рис. 29.16. На самом деле это не дерево, а ориентированный граф без циклов, но мы сохраняем традиционное название. Мы складываем 8 частичных произведений mS°\ ... , т7\ числа на стрелках указывают количество разрядов в складываемых числах (raW содержит га+г битов, о числе битов на выходе сумматора с запоминанием переносов см. упражнение 29.3-3). Последнее сложение (слагаемые имеют длины 2га - 1 и 2га, сумма имеет длину 2га) выполняется с помощью сумматора с предвычислением переносов.

Рис. 29.16 29.16 Дерево Wallacea для сложения частичных произведений т0, . . . , т7. Каждая стрелка обозначает число указанной разрядности.

29.3.4. Характеристики схемы

Обозначим глубину дерева Уоллеса для га слагаемых через D(n). На каждом уровне из каждых трёх чисел делается по два, да ещё два может остаться (как случилось на первом шаге на рис. 29.16), так что

Отсюда в силу теоремы 4.1 (случай 2) имеем D(n) = ©(lgra). Частичные произведения могут быть вычислены за время 0(1), каждый из шагов сложения с запоминанием переносов также требует времени 0(1), а сложение двух слагаемых размера ©(га) (последний шаг) требует времени 0(lg га). Поэтому общее время работы составляет 0(lg га).

Покажем теперь, что размер схемы равен ©(га2). Ясно, что он составляет не менее £7(га2), поскольку уже на верхнем ярусе имеется [~2га/3] блоков, каждый из которых содержит не менее га сумматоров. Оценим теперь размер схемы сверху. Поскольку результат сложения имеет 2га разрядов, число сумматоров в каждом из блоков не превосходит 2га. Остаётся показать, что число блоков (обозначим его С(га)) не превосходит 0(га). В самом деле,

0если га 2

1если га = 3

L>([2ra/3]) + l если га 4

1 если га = 3

откуда в силу теоремы 4.1 (случай 3) следует, что С(га) = 0(га). Таким образом, общее число элементов во всех сумматорах дере-

ва Уоллеса не превосходит 0(га2). Так же оценка справедлива для элементов, вычисляющих частичные произведения, а сумматор с предвычислением переносов имеет размер 0(га). Значит, размер всего умножителя равен 0(га2).

Хотя умножитель с помощью дерева Уоллеса имеет (асимптотически) тот же размер, что и матричный, и при этом работает (асимптотически) быстрее, он не столь удобен на практике, так как имеет нерегулярную структуру (и элементы трудно плотно разместить на плате). Поэтому используется промежуточный вариант: частичные произведения разбиваются на две половины, каждая складывается с помощью матричного умножителя, из 4 оставшихся чисел делает два с помощью двукрвтного использования сумматора с запоминанием переносов, наконец, два числа складываются с помощью сумматора с предвычислением переносов. Это почти вдвое уменьшает задержку по сравнению с одним матричным умножителем.

29.3.5. Упражнения

(г)

29.3-1 Докажите, что в матричном умножителе Vj=0 при j = 0,1,... ,i,i-\-n,i-\-n-\- 1,... ,2га- 1.

29.3-2 Измените схему матричного умножителя на рис. 29.14 так, чтобы в верхнем ряду из суммирующих элементов FA остался только один.

29.3-3 Пусть при сложении с запоминанием переносов из чисел ж, у и z получаются числа s и с. Пусть пх, пу, пх, пс, ns - разрядности соответствующих чисел и пх пу nz. Докажите, что ns = nz и

29.3-4 Показать, что дополнительное ограничение 0(1) на выходную степень всех проводов не мешает построить схему умножителя глубины О (lgra) и размера О (га2).

29.3-5 Постройте эффективную схему для деления двоичного числа на 3. (Указание. 0.010101... = 0.01 • 1.01 • 1.0001 •...).

29.3-6 Схема циклического сдвига (cyclic shifter, barrel shifter) имеет два входа ж = (жп ь жп 2,... , ж0) и s = (sm i, sm 2,... , s0), где m = [(lg га)] и выход у = (yn-i,yn-2, , Уо), получаемый из ж циклическим сдвигом на s позиций вправо: уг- = х+топ при [г = 0,1,... , га - 1). Как описать эту функцию в терминах умножения остатков?

nz если пу < nz nzA- \ если пу = nz

z 1

29.4. Тактированные схемы

Поскольку схема из функциональных элементов не содержит циклов, каждый элемент в ней используется только один раз. Элементы задержки позволяют использовать один и тот же функциональный элемент многократно (в разные моменты времени), что позволяет уменьшить размер схемы.

В этом разделе рассматриваются тактированные схемы (clocked circuits) для сложения и умножения. Устройство побитового сложения имеет размер 0(1) и складывает два га-разрядных числа за время О (га). Линейный умножитель умножает два га-значных числа за время 0(га) и имеет размер 0(га).

29.4.1. Устройство побитового сложения

На рис. 29.17 показана схема для сложения двух га-разрядных чисел а = (ага-ъ ап-2 , ао) и 6 = {bn-\, Ьп-2 ,Ьо), состоящая только из одного сумматора. Биты поступают на входы последовательно: сначала ао и bo, затем а\ и Ь\, и т. д. При этом выходной бит переноса надо подать на вход сумматора, но не сразу, а в момент поступления следующего разряда.

Рис. 29.17 Устройство побитового сложения. Между г-м и (г + 1)-м импульсами на входы сумматора FA поступают значения а, и Ь, извне и значение с, из регистра. Сумматор вычисляет значения s, и c;+i; последнее запоминается в регистре для следующего шага. В начальный момент регистр содержит значение со = 0. На рисунках (а)-(е) показаны пять этапов сложения чисел а = (1011) и Ъ = (1001)

Такая задержка осуществляется в тактированных схемах (clocked circuits). Такая схема содержит один или несколько регистров (элементов задержки), а также схему из функциональных элементов, входами которой являются, помимо входов тактированной схемы, выходы регистров. Её выходы служат выходами тактированной схемы, а также входами регистров. Как и раньше, схема из функциональных элементов не должна иметь циклов (обратная связь осуществляется только через элементы задержки).

Элемент задержки, или регистр (register) получает сигналы тактового генератора (clock), который через равные промежутки времени выдаёт тактовые импульсы (ticks). Мы считаем, что наши схемы имеют общий для всех регистров тактовый генератор (globally clocked circuits).

При каждом импульсе регистр запоминает текущее значение на входе. Вслед за этим это значение появляется на выходе, и тем самым поступает на входы схемы из фцнкциональных элементов.