Файл: 351-400.pdf

Ускорение целочисленного умножения  3 6 1

a v

Рис. 7.37. Суммирование ЧП с помощью дерева Уоллеса (вариант 1):

 a

 — логика

суммирования; б

 —

 точечная диаграмма

Умножитель (рис. 7.38) состоит из трех ступеней с высотами 4,3,2 и содержит

16 схем «И», 3 полусумматора, 5 полных сумматоров. Сложение векторов сумм

и переносов в последнем каскаде реализуется четырехразрядным сумматором с по-

следовательным распространением переноса, однако чаще для ускорения привле-
каются более эффективные схемы распространения переноса, например параллель-

ная.

Отметим, что избыточность кодирования, заложенная в алгоритм Уоллеса, при-

водит к тому, что возможно построение различных вариантов схемы дерева. Так,

на рис. 7.39 показана иная реализация дерева Уоллеса для четырехразрядных опе-
рандов.

Как видно, новый вариант схемы никакого выигрыша в аппаратурном плане не

дает.

Схема Уоллеса считается наиболее быстрой, но в то же время ее структура наи-

менее регулярна, из-за чего предпочтение отдается иным древовидным структу-
рам. Основная сфера использования умножителей со схемой Уоллеса — перемно-
жение чисел большой разрядности. В этом случае быстродействие имеет превали-
рующее значение.

При умножении чисел небольшой разрядности более распространена другая схема

сжатия суммирования ЧП — схема дерева Л. Дадда. В ее основе также лежит де-
рево Уоллеса, но реализуемое минимальным числом сумматоров.

3 6 2

 Глава 7. Операционные устройства вычислительных машин

Рис.

 7.38. Умножитель 4 х 4 со структурой дерева Уоллеса

Рис.

 7.39. Суммирование ЧП с помощью дерева Уоллеса (вариант 2):

 а —

 логика

суммирования;

 б —

 точечная диаграмма

Схема редукции, предложенная Л. Даддом, начинается с определения высоты

промежуточных матриц частичных произведений: d

1

-2 и

 d

j+l

 = [

1,5 х

 dj ]

, пока

dj < п.

 Значения для

 d

j

 приведены в табл. 7.3.

Ускорение целочисленного умножения  3 6 3

Таблица 7.3. Таблица высот промежуточных матриц в алгоритме Дадда

Так, 32-разрядный умножитель на базе дерева Дадда имеет высоты промежу-

точных матриц 29,19,13,9,6,4,3 и 2. На j-й от конца ступени умножителя исполь-
зуется минимальное число ПС и СМ, позволяющее сократить число битов в столбце

d

j

 Если высота столбца, включая переносы, равна h, то число полусумматоров  ( N

I 1 C

)

и полных сумматоров

 (N

CM

)

 составляет:

На рис. 7.40 описан умножитель  4 x 4 , реализующий алгоритм дерева Дадда.

Для этого требуется 16 схем "И", два полусумматора, четыре полных сумматора

и шестиразрядный сумматор. Схема содержит три ступени с высотами промежу-

точных матриц: 4,3 и 2. На этапе суммирования вектора сумм и вектора переносов
необходим (2n - 2)-разрядный сумматор.

Рис, 7.40. Суммирование ЧП с помощью дерева Дадда для случая чисел без знака:

 а —

 логика

суммирования;

 б —

 точечная диаграмма

Схема умножения чисел в дополнительном коде, рассмотренная примени-

тельно к матричному умножителю, может быть адаптирована

 и

 для умножите-

ля со схемой Дадда. В таком случае схема сжатия приобретает вид, показан-

ный на рис. 7.41.

3 6 4 Глава 7. Операционные устройства вычислительных машин

Рис.  7 . 4 1 . Суммирование ЧП в дополнительном коде с помощью дерева Дадда:

 а —

 логика

суммирования;

 б —

 точечная диаграмма

Различия методов Уоллеса и Дадда являются следствием разных подходов к ре-

шению задачи "компрессии" суммирования. Алгоритм Уоллеса ориентирован на

сжатие кодов как можно раньше, на самых ранних этапах, а алгоритм Дадда стре-

мится это сделать по возможности позже, то есть наибольший уровень сжатия от-
носит к завершающим стадиям.

Сравнивая схемы Уоллеса и Дадда, можно отметить, что число каскадов сжа-

тия в них одинаково, однако количество используемых полусумматоров и полных
сумматоров в схеме Дадда меньше (при подсчете числа элементов обычно не учи-
тывают многоразрядные сумматоры, предназначенные для окончательного сложе-
ния векторов сумм и переносов). С другой стороны, на этапе сложения векторов
сумм и переносов в варианте Уоллеса требуется сумматор с меньшим числом раз-
рядов (в нашем примере — 4 против 6).

У обеих схем имеется общий недостаток — нерегулярность структуры, особен-

но у дерева Уоллеса.

Схема перевернутой лестницы

 (overturned stairs), предложенная в [169], явля-

ет собой одну из попыток сделать древообразную структуру более регулярной,
а значит, облегчить ее реализацию в интегральном исполнении. «Лестница»стро-
ится из базовых блоков трех видов (рис. 7.42,

 а),

 которые авторы назвали «вет-

вью» (branch), «соединителем» (connector) и «корнем» (root).

Базовые элементы объединяются, образуя дерево, имеющее

 п

 входов, Подоб-

ная схема на 18 входов показана на рис. 7.42,

6.

 Как видно, дерево имеет достаточ-

Ускорение целочисленного умножений

  3 6 5

a

 б

Рис.

 7.42. Перевернутое дерево:

 а

 —

 базовые блоки;

 б

 — структура дерева на 18 входов

но регулярную структуру, однако нужно учитывать, что веса отдельных входов

различаются. Кроме того, конструкция умножителя получается сложной.

Сравнительная оценка схем умножения

с матричной и древообразной структурой

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

 T

L

 В ОДНОМ

логическом элементе.

Таблица

 7.4. Сравнение производительности умножителей в интегральном исполнении*

1

 n

 —

 разрядность сомножителей.