Файл: 351-400.pdf

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

щей пары разрядов множителя, путем обработки пары 00 как 01, пары 01 как

10, 10 —как 11, а 11 —как 00. В последних двух случаях фиксируется признак

коррекции.

Правила обработки пар разрядов множителя с учетом признака коррекции при-

ведены в табл. 7.2. После обработки каждой комбинации содержимое регистра
множителя и сумматора частичных произведений сдвигается на 2 разряда вправо.
Данный метод умножения требует корректировки результата, если старшая пара
разрядов множителя равна 11 или 10 и состояние признака коррекции единичное.

В этом случае к полученному произведению должно быть добавлено множимое.

Аппаратные методы ускорения умножения

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

шего разряда СЧП к старшему. Задержка из-за распространения переноса относи-

тельно велика, причем она повторяется при добавлении каждого ЧП.

Один из способов ускорения умножения состоит в изменении системы кодиро-

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

тичных произведений. Примером такого подхода может служить алгоритм Бута.

Еще один ресурс повышения производительности умножителя — использова-

ние более эффективных способов суммирования ЧП, исключающих затраты вре-
мени на распространение переносов. Достигается это за счет представления ЧП
в избыточной форме, благодаря чему суммирование двух чисел не связано с рас-
пространением переноса вдоль всех разрядов числа. Наиболее употребительной
формой такого избыточного кодирования является так называемая форма

 с сохра-

нением переноса.

 В ней каждый разряд числа представляется двумя битами

 cs,

 из-

вестными как перенос (с) и сумма

 (s).

 При суммировании двух чисел в форме

с сохранением переноса перенос распространяется не далее, чем на один разряд.

3 5 2

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

Это делает процесс суммирования значительно более быстрым, чем в случае сло-

жения с распространением переноса вдоль всех разрядов числа.

Наконец, третья возможность ускорения операции умножения заключается

в параллельном вычислении всех частичных произведений. Если рассмотреть об-
щую схему умножения (рис. 7.27), то нетрудно заметить, что отдельные разряды
ЧП представляют собой произведения вида a

i

b

j

,

 то есть произведение определен-

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

 п

2

 схем «И». При

перемножении чисел в дополнительном коде отдельные разряды ЧП могут иметь
вид a

i

b

j

 , a

i

b

j

 или a

i

b

j

 . Тогда элементы "И"заменяются элементами, реализую-

щими соответствующую логическую функцию.

Рис.

 7.27. Схема перемножения п-разрядных чисел без знака

Таким образом, аппаратные методы ускорения умножения сводятся:

-

 к

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

- к сокращению количества операций сложения;

-

 к уменьшению времени распространения переносов при суммировании частич-

ных произведений.

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

национных устройств.

Параллельное вычисление ЧП имеет место практически во всех рассматривае-

мых ниже схемах умножения. Различия проявляются в основном в способе сум-

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

 матричные

 и с

 древовидной структу-

рой.

 В обоих вариантах суммирование осуществляется с помощью массива взаи-

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

Различия в рамках каждой из этих групп выражаются в количестве используе-

мых сумматоров, их виде и способе распространения переносов, возникающих
в процессе суммирования.

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

В

 матричных умножителях

 суммирование осуществляется матрицей сумма-

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

дение. Поскольку промежуточные СЧП представлены в избыточной форме с со-

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

ет, что задержка в умножителях отталкивается только от «глубины» массива (чис-
ла строк сумматоров) и не зависит от разрядности операндов, если только в по-
следней строке матрицы, где формируется окончательная СЧП, не используется
схема с последовательным переносом.

Наряду с высоким быстродействием важным достоинством матричных умно-

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

нием разрядности сомножителей эта площадь увеличивается пропорционально

квадрату числа разрядов. Вторая проблема с матричными умножителями — низ-
кий уровень утилизации аппаратуры. По мере движения СЧП вниз каждая строка
задействуется лишь однократно, когда ее пересекает активный фронт вычислений.

Это обстоятельство, однако, может быть затребовано для повышения эффектив-

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

Ниже рассматриваются различные алгоритмы умножения и соответствующие им

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

Матричное умножение чисел без знака

Результат

 Р

 перемножения двух «-разрядных двоичных целых чисел

 А и В

 без зна-

ка можно описать выражением

Умножение сводится к параллельному формированию битов из

 п n

-разрядных

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

Схема известна как

 умножитель Брауна.

 На рис. 7.28 показан такой умножитель

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

умножения соответствует диагональ умножителя. Биты частичных произведений
(ЧП) вида

 a

i

b

j

 формируются с помощью элементов «И». Для суммирования ЧП

применяются два вида одноразрядных сумматоров с сохранением переноса: полу-
сумматоры (ПС)

1

 и полные сумматоры (СМ)

2

.

1

 Полусумматором называется одноразрядное суммирующее устройство, имеющее два входа для сла-

гаемых и два выхода — выход бита суммы к выход бита переноса.

2

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

да — выход бита суммы и выход бита переноса.

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

i

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

Матричный умножитель n

 х п

 содержит

 п

2

 схем «И»,

 п

 ПС и

 (п

2

 -

 2n) СМ. Если

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

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

ножителе составляет

 п

г

 + 2п + 5(п

2

 - 2n)

 -

 6п

г

 - 8п.

Быстродействие умножителя определяется наиболее длинным маршрутом рас-

пространения сигнала, который в худшем случае (пунктирная линия на рис. 7.28)
включает в себя прохождение одной схемы «И», двух ПС и (2n - 4) СМ. Полагая

задержки в схеме «И» и полусумматоре равными , а в полном сумматоре —

общую задержку в умножителе можно оценить выражением Чтобы со-

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

тора. Последнее, однако, не всегда желательно, поскольку это увеличивает число ис-

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

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

рядности: О(n).

Матричное умножение чисел в дополнительном коде

К сожалению, умножитель Брауна годится только для перемножения чисел без

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

Брауна. Прежде всего, напомним, что запись двоичного числа в дополнительном
коде (с дополнением до 2) имеет вид

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

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

дуль.

Исходя из приведенной записи, произведение

 Р

 двух «-разрядных двоичных

целых чисел

 А и В

 дополнительном коде (значение произведения и сомножите-

лей в дополнительном коде обозначим соответственно

 V(P), V(A)

 и

 V(B))

 можно

описать выражением

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

похожа на матрицу перемножения чисел без знаков (рис. 7.29). Отличие состоит
в том, что (2n - 2) частичных произведений инвертированы, а в столбцы

 п

 и (2n - 1)

добавлены единицы.

Рис. 7.29. Матрица перемножения п-разрядных чисел в дополнительном коде

Соответствующая схема матричного умножителя для четырехразрядных чисел

показана на рис. 7.30.

Здесь (2n - 2) частичных произведений инвертированы за счет замены элемен-

тов «И» на элементы «И-НЕ». Сумматор в младшем разряде нижнего ряда скла-
дывает 1 в столбце

 п

 с вектором сумм и переносов из предшествующей строки,

реализуя при этом следующие выражения:

Инвертор в нижней строке слева обеспечивает добавление единицы в столбец

(2n-1).