Методы ускорения умножения

Методы ускорения умножения принято делить [8, 11] на аппаратные и логические. Как те, так и другие требуют дополнительных затрат оборудования. При использовании аппаратных методов дополнительные затраты оборудования прямо пропорциональны числу разрядов в операндах. Эти методы вызывают усложнение схемы операционного автомата АЛУ.

Дополнительные затраты оборудования при реализации логических методов ускорения умножения не зависят от разрядности операндов. Усложняется в основном схема управления АЛУ. В ЭВМ для ускорения умножения часто используются комбинации этих методов.

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

Пример реализации умножения с использованием n-входового сумматора показан на рис. 3.24.

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

Метод табличного умножения (рис. 3.25) позволяет получить произведение за один такт при условии, что вся таблица умножения (результаты умножения всевозможных пар п -разрядных сомножителей!) будет размещена в памяти. Очевидно, для этого понадобится запоминающее устройство объемом 2^2п 2n-разрядных слов (точно таким же способом можно выполнять и другие "длинные" операции — деление, вычисление функций). Так, для организации 8-разрядного умножителя потребуется память объемом 2¹⁶ х16 бит=128 Кбайт, что для современного уровня развития интегральной технологии не кажется чрезмерным.

(Страница66)

Однако для 16-разрядного АЛУ умножитель "потянет" уже на 2³² х32 бит=16 Гбайт! Что касается современных 32-разрядных процессоров, то к расчету потребности в памяти для таких умножителей даже страшно приступать.

Рис. 3.24. Матричное умножение

Рис. 5.25. Табличное умножение

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

Рассмотрим этот способ умножения подробнее. Пусть n — четное. Тогда каждый из двух сомножителей можно представить конкатенацией двух полей одинаковой разрядности n/2: А = A_hA_l, B=B_hB_l. В этом случае произведение можно представить следующим выражением:

(3.28)

Таким образом, располагая, например, таблицей умножения 8x8, можно получить произведение двух 16-разрядных сомножителей, сложив (с соответствующим сдвигом) всего 4 слагаемых. Проиллюстрируем этот метод на простом примере.

Пусть требуется перемножать 4-разрядные числа без знака. Построим таблицу умножения 2x2 (при рассмотрении примера не будем включать в нее пары сомножителей, когда один из них равен нулю, а так же пары сомножителей, симметричные уже включенным) — рис. 3.26.

Рис. 3.26. Вспомогательная таблица умножения

Пример 3.22

Выполним умножение 6x10=60 или в двоичном коде 01.10x10.10=00111100. Из таблицы получаем частичные произведения: A_lхB_l,=10x10=0100, A_lхB_h=10x10=0100, A_hxВ_l,= 01x10=0010, A_hxB_h =01x10=0010.

Теперь сложим частичные произведения, предварительно сдвинув их в соответствии с (3.28). Результат — на рис. 3.27.

Рис 3.27. Результат выполнения примера 3.22

Выполним умножение 7х11=77 или в двоичном коде 01.11x10.11=01001101.

Из таблицы получаем частичные произведения: A_l х B_l =11х11=1001, A_lxB_h =11x10=0110, A_hxB_l= 01x11=0011, A_h xB_h= 01x01=0001.

Теперь сложим частичные произведения, предварительно сдвинув их в соответствии с (3.28). Результат — на рис. 3.28.

Рис. 3.28. Результат выполнения примера 3.23

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

Таблица 3.3. Действия

Комбинация	Действие	Добавлено
	Сдвиг — Сдвиг
	Сложение — Сдвиг — Сдвиг	А
	Сдвиг — Сложение — Сдвиг	2А
	Сложение — Сдвиг — Сложение — Сдвиг	3А=4А - А

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

□ при 00 просто произвести сдвиг на два разряда;

□ при 01 прибавить к сумме частичных произведений множимое и произвести сдвиг на два разряда;

□ при 10 прибавить к сумме частичных произведений удвоенное множимое и произвести сдвиг на два разряда;

□ при 11 вычесть из суммы частичных произведений множимое (или добавить обратный (дополнительный) код множимого), произвести сдвиг на два разряда и добавить 1 к следующей (старшей) паре цифр множителя. При классическом методе умножения двоичных п -разрядных чисел согласно выражению (3.26) потребуется n сдвигов суммы частичных произведений и n/2 (в среднем) сложений множимого с суммой частичных произведений. Один из методов ускорения операции умножения — анализ сразу двух разрядов множителя. Это позволит получить результат, применяя n/2 сдвигов и (в среднем) 3n/8 сложений/вычитаний.