Файл: 347-350.pdf

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

ны (2n разрядов). Поскольку число итераций в операции умножения определяет-
ся количеством цифровых разрядов множителя, окончательный результат может
размещаться в разрядной сетке двойного слова неверно, что и имеет место при пе-
ремнбжении целых чисел (рис. 7.23). Как видно, младший разряд произведения
целых чисел, имеющий вес 2°, размещается в позиции двойного слова, соответ-
ствующей весу 2

1

. Таким образом, для правильного расположения произведения в

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

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

сдвиг не нужен (см. рис. 7.23). Это обстоятельство необходимо принимать во вни-
мание при построении умножителя для чисел в форме с плавающей запятой, где

участвующие в операции мантиссы представлены в нормализованном виде, то есть

правильными дробями.

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

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

лишних разрядов, либо округление.

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

Методы ускорения умножения можно условно разделить на аппаратные и логи-

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

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

Логические методы ускорения умножения

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

группы:

-

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

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

Реализация и тех и других требует введения дополнительных цепей сдвига в ре-

гистры.

Рассмотрим первую группу логических методов.

Алгоритм Бута

В основе алгоритма Бута [63] лежит следующее соотношение, характерное для
последовательностей двоичных цифр;

где

 т

 и

 k —

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

пример, Это означает, что при наличии в множителе групп из не-
скольких единиц (комбинаций вида 011,110), последовательное добавление к СЧП

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

множимого с нарастающим весом (от 2

k

 до 2

m

) можно заменить вычитанием из СЧП

множимого с весом 2* и прибавлением к СЧП множимого с весом 2

и+|

.

Как видно, алгоритм предполагает три операции: сдвиг, сложение и вычитание.

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

ство — он в равной степени применим к числам без знака и со знаком.

Алгоритм Бута сводится к перекодированию множителя из системы (0, 1)

в избыточную систему (-1,0,1), из-за чего его часто называют перекодированием

Бута (Booth recoding). В записи множителя в новой системе 1 означает добавле-

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

изводится сдвиг множимого влево или суммы частичных произведений вправо.
Реализация алгоритма предполагает последовательный в направлении справа нале-
во анализ пар разрядов множителя — текущего b

i

, и предшествующего

 b

i

(b

i

b

i-1

).

Для младшего разряда множителя (i - 0) считается, что предшествующий разряд
равен 0, то есть имеет место пара b

0

0. На каждом шаге i

(i =

 0,1,.„,

 п

 - 1) анализиру-

ется текущая комбинация

 b

i

(b

i

b

i-1

).

Комбинация 10 означает начало цепочки последовательных единиц, и в этом

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

Комбинация 01 соответствует завершению цепочки единиц, и здесь множимое

прибавляется к СЧП.

Комбинация 00 свидетельствует об отсутствии цепочки единиц, а 11 — о на-

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

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

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

Описанную процедуру рассмотрим на примерах (используется вариант со сдви-

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

Пример

 1.0110x0011-00010010 (в десятичном виде 6хЗ-18), После переко-

дирования Бута множитель (0,0,1,1) приобретает вид (0,1,0,-1).

В начале сумма частичных произведений принимается равной нулю — 00000000.

Полагается, что младшему разряду множителя предшествовал 0. Дальнейший про-
цесс поясняет рис. 7.24.

Начало цепочки Внутри цепочки Конец цепочки Вне цепочки единиц

единиц - (-А) единиц единиц - (+А)

Рис. 7.24. Пример 1 умножения (6 х 3) в соответствии с алгоритмом Бута

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

  3 4 9

Пример

 2.

 1

100x0011 = 11110100 (в десятичной записи  - 4 x 3 --12).

Процесс вычисления иллюстрирует рис. 7.25.

Рис.

 7.25. Пример 2 умножения (-4 х 3) в соответствии с алгоритмом Бута

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

рований равно n/2, где

 п —

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

Модифицированный алгоритм Бута

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

 п/2.

 В модифицированном алгоритме производится перекоди-

ровка цифр множителя из стандартной двоичной системы (0,1) в избыточную си-

стему (-2, -1, 0, 1, 2), где каждое число представляет собой коэффициент, на

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

зируются три разряда множителя

 b

i

(b

i

b

i-1

)(два текущих и старший разряд из пре-

дыдущей тройки) и, в зависимости от комбинации 0 и 1 в этих разрядах, выпол-

няется прибавление или вычитание множимого, прибавление или вычитание

удвоенного множимого, либо никакие действия не производятся (табл. 7.1).

Таблица 7.1

. Логика модифицированного алгоритма Бута

Пример вычисления произведения 011001 х 101110 = 011000111110 (в деся-

тичном виде 25 х (-18) = -450) показан на рис. 7.26.

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

Рис. 7.26. Пример умножения (18 х (-25)в соответствии с модифицированным

алгоритмом Бута

Алгоритм Лемана

Еще большее сокращение количества сложений может дать модификация, пред-

ложенная Леманом [151]. Здесь, даже при наименее благоприятном сочетании цифр
множителя, количество операции сложения не превышает величины n/2, а в сред-
нем же оно составляет я/3. Суть модификации заключается в следующем:

-

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

 k-й

 позиции, то вместо

вычитания в

 k-й

 позиции и сложения в

 (k

 +1 )-й позиции достаточно выпол-

нить только сложение в k-й позиции;

- если две группы единиц разделены нулем, стоящим в k-й позиции, то вместо

сложения в k-й позиции и вычитания в

 (k

 + 1)-й позиции достаточно выпол-

нить только вычитание в

 k-й

 позиции.

Обработка двух разрядов множителя за шаг

Из второй группы логических методов остановимся на умножении с обработкой
за шаг двух разрядов множителя (IBM 360/370). В принципе это более эффектив-
ная версия алгоритма Бута. Анализ множителя начинается с младших разрядов.

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

дующие действия:

- 00 — простой сдвиг на два разряда вправо суммы частичных произведений

(СЧП);

- 01 — к СЧП прибавляется одинарное множимое, после чего СЧП сдвигается на

2 разряда вправо;

- 10 — к СЧП прибавляется удвоенное множимое, и СЧП сдвигается на 2 разря-

да вправо;

- 11 — из СЧП вычитается одинарное множимое, и СЧП сдвигается на 2 разряда

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

бавления утроенного, для корректировки результата к СЧП перёд выполнением
сдвига надо было бы прибавить учетверенное множимое. Но после сдвига на два
разряда вправо СЧП уменьшается в четыре раза, так что на следующем шаге дос-
таточно добавить одинарное множимое. Это учитывается при обработке следую-