14. УМНОЖИТЕЛЬ
Умножение
Def
===
УМНОЖИТЕЛЬ - функциональный узел, который умножает 2 числа.
Что такое умножение:
a * b = a * a * a * ... * a * a * a
| |
+-------------------------+
b раз
Что такое умножение в двоичной системе:
X * 0 = 0
X * 1 = X
X * Y = X AND Y
таким образом умножение в двоичной системе сводится к сдвигу и
сложению:
10101
* 10111
-------------
10101
10101
+ 10101
00000
10101
-------------
111100011
Типы умножителей
Умножение ----------------------------+
/ | \ |
ПАРАЛЕЛЬНЫЕ УМНОЖИТЕЛИ ПОСЛЕДОВАТЕЛЬНЫЙ
Аппаратный Табличный Комбинированный УМНОЖИТЕЛЬ
умножитель метод метод
Время: долго быстро средне очень много
Элементы: много очень много относительно мало мало
Последовательный умножитель
Микропрограмная реализация последовательного умножителя
result = 0;
temp = Y;
for i = 0 to N do
begin
if (bit(i,X) == 1) then
begin
result = result + temp;
end;
temp = SHIFT_RIGHT(temp,1);
end;
Проблема в том, что очень много сложений занимают очень много времени.
Поэтому все оптимизации занимаются уменьшением числа полных сложений
(когда происходит перенос).
Знаковое и беззнаковое умножение
Умножение знаковых и беззнаковых чисел различное:
ab
* cd
-----------
00bd БЕЗЗНАКОВЫЕ
+ 0ad
0cb
ac
-----------
ab
* cd
-----------
SSbd ЗНАКОВЫЕ
+ Sad (S = знаковое расширение частичного произведения)
Scb
ac
-----------
Обратите внимание:
младшие N байт произведения (N*N) не зависят от знака
поэтому в RISC микропроцессорах обычно используют три команды для
умножения:
MULL Multiply Low (младшие N бит)
MULHS Multiply High Signed (старшие N бит знаковое *)
MULHU Multiply High Unsigned (старшие N бит беззнаковое *)
Пример знакового последовательного умножителя:
Сокращение числа частных произведений
Один из методов заключается в вычислении произведений не побитово, а поблочно
и последующего их сложения (умножение в столбик).
Значение произведения блока может быть вычислено быстрым аппаратным
умножителем или табличным методом.
Умножение в столбик:
+------+------+
| a | b |
* +------+------+
| c | d |
+------+------+
=====================================
+-------------+
| bd |
+-------------+
+--------------+
| ad |
+ +--------------+
+--------------+
| cb |
+--------------+
+--------------+
| ac |
+--------------+
=====================================
+-----------------------------+
| Result |
+-----------------------------+
Табличный метод умножения
Табличный метод:
Строится ПЗУ содержащее таблицу умножения.
0 и 1 - особые случаи, их можно обработать аппаратно отдельно.
Пример такой таблицы для умножителя 3x3 = > 6
(данные в таблице представленны в 16-ричной системе счистления):
Можно хранить не всю таблицу а ее половину т.к. она симметрична.
*|2 3 4 5 6 7
-+-----------------
2|04 06 08 0A 0C 0E
3| 09 0C 0F 12 15
4| 10 14 18 1C
5| 19 1E 23
6| 24 2A
7| 31
Время работы для 4x4 = время дешифратора(8бит) + L (транзистор)
= (инвертор + 3 * И) + L (транзистор) = 5L
Методы быстрого аппаратного умножения
Матричный (n-частичных произведений суммируются в n-каскадах)
Бута (уменьшенно количество частных произведений)
Уолеса (параллельное сложение частных произведений)
NMM (умножение без сложения)
Index Prev Next