Файл: 351-400.pdf

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

Содержимое таблицы плюс некоторые не включенные в нее данные позволяют

сделать следующие выводы. Наиболее быстро работают умножители, построен-

ные по схеме Бута, а также имеющие древовидную структуру, в частности дерево

Дадда. Для операндов длиной в 16 разрядов и более наиболее привлекательной

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

оборудования. Максимально быстрое выполнение операции умножения обеспе-
чивает сочетание алгоритма Бута и дерева Уоллеса. С другой стороны, достаточно

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

дает схема Бо-Вули. В плане потребляемой мощности наиболее экономичными
являются умножители, построенные по схемам Брауна и Пезариса. Несмотря на

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

Конвейеризация параллельных умножителей

В матричной и древовидной структурах параллельных умножителей заложен еще

один потенциал повышения производительности — возможность конвейеризации.

При конвейеризации весь процесс вычислений разбивается на последовательность
законченных шагов. Каждый из этапов процедуры умножения выполняется на сво-
ей ступени конвейера, причем все ступени работают параллельно. Результаты, по-
лученные на i-й ступени, передаются на дальнейшую обработку в (i + 1)-ю сту-
пень конвейера. Перенос информации со ступени на ступень происходит через
буферную память, размещаемую между ними (рис. 7.43).

Рис. 7.43. Структура конвейерного умножителя

Выполнившая свою операцию ступень помещает результат в буферную память

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

щиеся в буферной памяти на ее входе. Синхронность работы конвейера обеспечи-

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

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

ступенью конвейера

 t

i

 и задержкой в элементе буферной памяти

 t

i

 t

= max (

t

1

 ,

t

2

,

...

 t

k

) + t

i

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

конкретной пары сомножителей в конвейерном умножителе не только не умень-
шается, но даже несколько увеличивается за счет задержек в буферной памяти при
последовательном перемножении последовательностей пар сомножителей, дости-
гаемый выигрыш весьма ощутим. Действительно, в конвейерном умножителе из

 k

ступеней перемножаемые данные могут подаваться на вход с интервалом в

 к

 раз

меньшим, чем в случае обычного умножителя. В том же темпе появляются и ре-

зультаты на выходе.

Схема конвейера легко может быть применена к матричным и древовидным

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

го матричного умножителя на рис. 7,44 приведена схема

 4x4.

 Черными прямо-

угольниками обозначены триггеры-защелки, образующие буферную память.

Рис. 7.44. Конвейеризированный матричный умножитель

Конвейеризация матричных умножителей на уровне строк сумматоров может

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

- отказа от использования идеи конвейеризации между входными схемами "И"

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

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

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

его равным удвоенному времени срабатывания полного сумматора;

- отказом от формирования всех

 п

г

 битов частичных произведений в самом нача-

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

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

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

Кроме того, количество каскадов компрессии также значительно меньше. Это

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

мой Дадда.

Рис. 7.45. Древовидный конвейеризированный умножитель со схемой Дадда

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

В правой части рисунка указано количество триггеров-защелок, необходимых

в каждой ступени конвейера. Как видно, в умножителе Дадда  8 x 8 требуются
243 триггера, не считая дополнительных триггеров для конвейеризации последнего

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

крашено за счет увеличения времени, выделяемого на выполнение операций

в ступени конвейера. Это позволяет убрать некоторые из триггеров.

При конвейеризации умножителя на базе дерева Уоллеса требуется меньше

триггеров-защелок, поскольку в этой схеме основное сжатие суммы частичных
произведений происходит на более ранних этапах. Кроме того, для заключитель-
ного суммирования векторов сумм и переносов используется более «короткий»
сумматор.

Рекурсивная декомпозиция операции умножения

Как правило, аппаратные умножители, построенные на рассмотренных принци-

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

 рекурсивную декомпозицию операции умножения.

 Так, для

построения умножителя  8 x 8 можно использовать четыре модуля типа 4x4. Мно-
жимое

 А

 разбивается на четыре старших

 (A

h

)

 и четыре младших

 (А

1

)

 разряда. Мно-

житель

 В

 таким же образом разбивается на части

 В

h

 и

 В

1

 Четыре модуля типа  4 x 4

вычисляют соответственно произведения

 A

h

xB

h

 , A

h

xB

h

 A

1

xB

h

 , A

1

x

В

1

,.

 На выхо-

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

частичным произведениям в разрядах: 15—8,11-4, снова 11-4 и 7-0. Окончатель-
ный результат формируется путем суммирования этих четырех частичных произ-
ведений с учетом их положения в разрядной сетке (рис. 7.46).

Рис. 7.49. Декомпозиция операции умножения

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

Целочисленное деление

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

Рис. 7.47. Общая схема операции деления

Задача сводится к вычислению частного

 Q

 и остатка

 S:

Деление выражается как последовательность вычитаний делителя сначала из

делимого, а затем из образующихся в процессе деления частичных остатков  ( 4 0 ) .
Делимое обычно представляется двойным словом

 (2п

 разрядов),

делитель частное и остаток име-

ют разрядность

 п.

Операция выполняется за л итераций и может быть описана следующим образом:

После

 п

 итераций получается

Частное от деления 2n-разрядного числа на n-разрядное может содержать бо-

лее, чем

 п

 разрядов. В этом случае возникает переполнение, из-за чего перед вы-

полнением деления необходима проверка условия

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

в старших

 п

 разрядах делимого, меньше делителя.

Помимо этого требования, перед началом операции необходимо исключить

возможность ситуации деления на 0.

Реализовать деление можно двумя основными способами:

- с неподвижным делимым и сдвигаемым вправо делителем;
я с неподвижным делителем и сдвигаемым влево делимым.

Недостатком первого способа является потребность иметь в устройстве деле-

ния сумматор и регистр двойной длины. Второй способ позволяет строить дели-