|
|
100000 |
|
|
|
||||
|
12 |
|
000010 |
|
|
|
|
000111 |
|
|
15 |
001 |
|
000101 |
|
|
000000 |
|
|
|
19 |
|
|
|
|
|
000001 |
|
|
|
10 |
|
|
|
000101 |
000001 |
|
|
|
|
13 |
|
111110 |
|
|
|
|
111000 |
|
|
15 |
000 |
|
111100 |
|
|
000010 |
|
|
|
18 |
|
|
|
|
|
000010 |
|
|
|
11 |
|
000101 |
111110 |
111110 |
|
|
000111 |
|
|
14 |
|
|
000101 |
|
|
|
|
|
|
17,20 |
|
000010 |
000010 |
000010 |
000010 |
|
000000 |
|
3.4. Алгоритм ускоренного умножения чисел с фиксированной запятой
Операция умножения относится к длинным операциям. Для уменьшения времени ее выполнения существуют методы ускорения умножения. Они делятся на аппаратурные и логические. Как те, так и другие требуют дополнительных затрат оборудования. При использовании аппаратурных методов дополнительные затраты оборудования прямо пропорциональны числу разрядов в операндах. Эти методы вызывают усложнение схемы АЛУ.
Дополнительные затраты оборудования при реализации логических методов ускорения не зависят от разрядности операндов. Усложняется в основном схема управления АЛУ. В ЭВМ для ускорения умножения часто используются комбинации этих методов.
К аппаратурным методам ускорения умножения относятся ускорение выполнения операций сложения и сдвига, позволяющих за один такт производить сдвиг информации в регистрах сразу на несколько разрядов, совмещение по времени операций сложения и сдвига, построение комбинационных схем множительных устройств, реализующих «табличное» умножение.
Среди логических методов наиболее распространены методы, позволяющие за один цикл умножения обработать несколько разрядов множителя.
Рассмотрим метод ускоренного умножения n-разрядных целых чисел без знака (при четном n) по формуле:
где – значения i-го и i+1-го разрядов множителя Y, - частичная сумма для i-го и i+1-го разрядов множителя, а умножение на 2-2 осуществляется путем сдвига числа на два разряда вправо. В зависимости от данной пары разрядов к сумме частичных произведений прибавляются значения, указанные в табл. 3.4.
В многофункциональное АЛУ на рис. 4.1 для выполнения ускоренного умножения необходимо добавить триггер Т (признак коррекции), предназначение которого будет описано ниже.
Табл. 3.4. Изменение суммы частичных произведений
Значение, которое
необходимо прибавить к сумме частичных
произведений
00
0
01
X
10
2×X
11
3×X
Алгоритм операции ускоренного умножения целых чисел без знака в многофункциональном АЛУ приведён на рис. 3.16. В блоках микрооперации, выполняемые в разных тактах, разделяются горизонтальной чертой.
Последовательность выполнения операции ускоренного умножения на функциональных узлах АЛУ можно обобщить и выделить следующие этапы:
- начальная установка;
- вычисление сумм частичных произведений.
На рис. 3.16 этапы выполнения операции умножения разделены пунктирной линией.
Рис. 3.16. Микропрограмма ускоренного
умножения целых чисел
Рассмотрим особенности этапа вычисления сумм частичных произведений. На данном этапе за один цикл умножения анализируется сразу два разряда множителя (). В зависимости от данной пары разрядов к сумме частичных произведений прибавляются значения указанные в табл. 3.4.
Рассмотрим случаи, указанные в табл. 3.4, подробнее:
- при = 00 к сумме частичных произведений прибавляется 0 и производится ее сдвиг на два разряда вправо;
- при = 01 к сумме частичных произведений прибавляется одинарная мантисса множимого и сумма частичных произведений сдвигается на два разряда вправо;
- при = 10 прибавляется удвоенная мантисса множимого и сумма частичных произведений сдвигается на два разряда вправо;
- при = 11 вместо прибавления к сумме частичных произведений утроенной мантиссы множимого из суммы частичных произведений вычитается одинарная мантисса множимого и сумма частичных произведений сдвигается на два разряда вправо. Справедливость данной замены следует из равенства: 3×X = -X + 4×X, где 4×X должно быть прибавлено к сумме частичных произведений в следующем цикле. Так как после сдвига на два разряда вправо сумма частичных произведений уменьшится в 4 раза, то в следующем цикле необходимо прибавить не 4×X, а значение в четыре раза меньше, т.е. X.
При анализе следующей пары разрядов множителя необходимо учитывать величину коррекции предыдущей пары разрядов. Необходимость коррекции фиксируется в триггере коррекции Т. При этом:
Т =
Рассмотрим пример ускоренного умножения 6-разрядных чисел.
Пример. Пусть X = 011101b – множимое,
Y = 011101b – множитель.
Вычислить Z – произведение.
Оформим вычисление в виде табл.3.5. Правила обработки пар разрядов множителя с учетом триггера коррекции приведены в табл. 3.6.
Табл. 3.5. Пример вычисления произведения
X
(множимое)
Сумма
частичных произведений
Y
(множитель)
Триггер коррекции Т
К сумме частичных произведе-ний прибавлено
011101
000000
011101
0
000000
011101
011101
000111
011101
0
X
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
При использовании материалов активная ссылка на источник обязательна.