Файл: 351-400.pdf

3 5 6

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

Рис.

 7.30. Матричный умножитель для четырехразрядных чисел в дополнительном коде

Алгоритм Бо-Вули

Несколько иная схема матричного умножителя, также обеспечивающего умноже-
ние чисел в дополнительном коде, была предложена Бо и Bули [61]. В алгоритме

Бо-Вули произведение чисел в дополнительном коде представляется следующим

Матрица умножения, реализующая алгоритм, приведена на рис. 7.31, а соот-

ветствующая ей схема умножителя — на рис. 7.32.

По ходу умножения частичные произведения, имеющие знак «минус», смеща-

ются к последней ступени суммирования. Недостатком схемы можно считать то,

что на последних этапах работы требуются дополнительные сумматоры, из-за чего
регулярность схемы нарушается.

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

  3 5 7

Рис. 7.31

. Матрица перемножения п-разрядных чисел согласно алгоритму Бо-Вули

Рис.

 7.32. Матричный умножитель для четырехразрядных чисел

в дополнительном коде по схеме Бо-Вули

Алгоритм Пезариса

Еще один алгоритм для вычислений произведения чисел в дополнительном коде

был предложен Пезарисом [181].

При представлении числа в дополнительном коде старший разряд числа имеет

отрицательный вес. Для учета этого обстоятельства Пезарис выдвигает идею ис- .
пользовать в умножителе четыре вида полных сумматоров (рис, 7.33).

3 5 8

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

Рис.

 7.33. Виды сумматоров, применяемых в матричном умножителе Пезариса

В сумматоре типа СМО, который фактически является обычным полным сум-

матором, все входные данные

 (х, у, z

) имеют положительный вес, а результат ле-

жит в диапазоне 0-3. Этот результат представлен двухразрядным двоичным чис-
лом

 cs,

 где

 с

 и s также присвоены положительные веса. В остальных трех типах

сумматоров некоторые из сигналов имеют отрицательный вес. Схема умножения

в рассматриваемом методе показана на рис. 7.34.

Рис. 7.34.

 Матрица перемножения n-разрядных чисел согласно алгоритму Пеэариса

Здесь знак "минус"- трактуется следующим образом: -1 = -2 * 1 + 1;  - 0 = - 2 *

*0 + 0. Схема умножителя, реализующего алгоритм Пезариса, приведена на рис. 7.35,

По сравнению с умножителем Бо-Вули, схема Пезариса имеет более регуляр-

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

сумматоров.

Древовидные умножители

Сократить задержку, свойственную матричным умножителям, удается в схемах,
построенных по древовидной структуре. Если в матричных умножителях для сум-
мирования

 п

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

видных схемах количество ступеней сумматоров пропорционально log

2

 n(рис. 7.36).

Соответственно числу ступеней суммирования сокращается и время вычисле-

ния СЧП. Хотя древовидные схемы быстрее матричных, однако при их реализа-
ции требуются дополнительные связи для объединения разрядов, имеющих оди-
наковый вес, из-за чего площадь, занимаемая схемой на кристалле микросхемы,
может оказаться даже больше, чем в случае матричной организации сумматоров.
Еще одна проблема связана с тем, что стандартное двоичное дерево не является

самой эффективной древовидной иерархией, поскольку не позволяет в полной мере

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

Рис. 7.35. Матричный умножитель для четырехразрядных чисел

в дополнительном коде по схеме Пеэариса

Рис. 7.36. Суммирование частичных произведений в умножителях: а — о матричной

структурой;

 б

 — со структурой двоичного дерева

воспользоваться возможностями полного сумматора (имеющего не два, а три вхо-

да), благодаря чему можно одновременно суммировать сразу три входных бита.

По этой причине на практике в умножителях с древовидной структурой применя-

ют иные древовидные схемы. С другой стороны, такие схемы не столь регулярны,
как двоичное дерево, а регулярность структуры — одно из основных требований
при создании интегральных микросхем.

Древовидные умножители включают в себя три ступени:

-

 ступень формирования битов частичных произведений, состоящую из n

2

 эле-

ментов «И»;

- ступень сжатия частичных произведений — реализуется в виде дерева парал-

лельных сумматоров (накопителей), служащего для сведения частичных про-

изведений к вектору сумм и вектору переносов. Сжатие реализуется несколь-

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

кими рядами сумматоров, причем каждый ряд вносит задержку, свойственную
одному полному сумматору;

-

 ступень заключительного суммирования, где осуществляется сложение векто-

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

ным

 O(log

2

(n)).

Известные древовидные умножители различаются по способу сокращения ч пе-

ла ЧП. При использовании в умножителе СМ и ПС их обычно называют счетчи-

ками (3,2) и (2,2) соответственно. Связано это с тем, что код на выходах

 cs,

 как и в

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

Процесс «компрессии» СЧП завершается формированием двух векторов — век-

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

упомянутых векторов.

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

три древовидных схемы суммирования ЧП: дерево Уоллеса, дерево Дадда и пере-

вернутое ступенчатое дерево.

В наиболее общей формулировке дерево Уоллеса — это оператор с

 п

 входами

и log

2

n выходами, в котором код на выходе равен числу единиц во входном коде.

Вес битов на входе совпадает с весом младшего разряда выходного кода. Простей-
шим деревом Уоллеса является СМ. Используя такие сумматоры, а также полу-
сумматоры, можно построить дерево Уоллеса для перемножения чисел любой
разрядности, при этом количество сумматоров возрастает пропорционально вели-

чине log

2

n. В такой же пропорции растет время выполнения операции умножения.

Согласно алгоритму Уоллеса, строки матрицы частичных произведений груп-

пируются по три. Полные сумматоры используются для сжатия столбцов стремя
битами, а полусумматоры — столбцов с двумя битами. Строки, не попавшие
в набор из трех строк, учитываются в следующем каскаде редукции. Количе-
ство строк в матрице (ее высота) на j-й ступени определяется выражениями
w

о

 = n и w

j + l

 =2[w

j

3] + (w

j

 mod 3),пока w

j

 >=2

В 32-разрядном умножителе на базе дерева Уоллеса высоты матриц ЧП после-

довательно уменьшаются в последовательности: 22,15, 10, 7, 5, 4, 3 и 2. Логика

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

жителе  4 x 4 показана на рис, 7.37,

 а.

 Для пояснения структуры дерева сумматоров

часто применяют так называемую точечную диаграмму (рис. 7.37,

6).

 В ней точки

обозначают биты частичных произведений, прямые диагональные линии представ-

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

маторов. Хотя на рис. 7.37,

 а

 в третьем каскаде показаны три строки, фактически

после редукции остаются лишь две первых, а третья лишь отражает переносы, ко-
торые учитываются при окончательном суммировании. Этим объясняется кажу-
щееся отличие от точечной диаграммы.