К. Хамахер, З. Вранешич, С. Заки - Организация ЭВМ - 5-е издание (2003) (1114649), страница 98
Текст из файла (страница 98)
Это ступенчатый путь, включающий по две ячейки с правого края каждой строки, а в конце — все ячейки нижней строки. Если предположить, что при прохождении сигналов от входов к выходам блока полного сумматора возникают две задержки в вентилях, весь этот путь для массива п х л сопровождается возникновением 6(п — 1) — 1 вентилъных задержек, с учетом задержки в первом вентиле И, который имеется в каждой ячейке (см. упражнение 6.12). В первой строке массива нужны только вентили И, поскольку входящее частичное произведение РРО равно нулю. Мы учли это, рассчитывая задержку, Операция умножения обычно входит в набор машинных команд процессора. В высокопроизводительных процессорах значительная часть микросхемы отведена под выполнение арифметических операций над целочисленными операндами и операндами с плавающей запятой.
(Об операциях с плавающей запятой рассказывается далее в этой главе.) Хотя структура описанного комбинационного умножителя проста и понятна, для умножения чисел реального размера (32 или 64 разряда) он должен содержать очень много вентилей. Можно выполнять умножение иначе, сочетая технологию комбинационной матрицы (рис. 6.6) с последовательной технологией, в которой меньше комбинационной логики. Простейший способ умножения основан на использовании имеющейся в АДУ схемы сумматора, предназначенной для выполнения ряда последовательных шагов.
На рис. 6.7, а демонстрируется, как взаимодействуют аппаратные элементы в процессе последовательного умножения. Для умножения используется один л-разрядный сумматор. Он и раз производит ту операцию, которую выполняет каждая строка сумматоров с последовательным переносом в схеме, предложенной вашему вниманию на рис. 6.6, б.
В регистрах А и О формируется частичное произведение РРй а каждый бит д; множителя, изначально хранящегося в регистре О, генерирует сигнал А/ХА (Аг(г(/о(оаЫ). Этот сигнал управляет прибавлением множимого М к произведению РР1 для получения значения РР(1 + 1). Все произведение вычисляется за п циклов. Длина частичного произведения на каждом шаге увеличивается на один разряд. С самого начала в регистре А содержится вектор РР0, состоящий из п нулей. Перенос из сумматора сохраняется в триггере С, показанном слева от регистра А.
6.3. Умножение положительных чисел 417 Регистр А (первоначально содержит О) Исходная конфигурация 1011 1 1 О! !О! 1О 0 0 0~ С 0 0 А 1 1 0 1 0110 Первый цикл 1 0 1 1 Сложение 1101 Сдвиг 1 1 0 1 Сложение 1110 Сдвиг 1 1 1 0 Нет сложения1 Третий цикл 1111 Сдвиг 1 1 1 1 Сложение 1111 Сдвиг Второй цикл 1 0011 01001 01001 00100 Четвертый цикл 10001 01000 Произведение рис. 6.7.
Последовательный двоичный умножитепги конфигурация (ар пример умнолсения (6! Процесс умножения начинается с того, что множимое загружается в регистр М, множитель — в регистр Я, а С и А заполняются нулями. В конце каждого цикла С, А и Я сдвигаются на один разряд вправо, чтобы частичное произведение 41В Глава 6. Арифметика 6.4. Умножение чисел со знаком Настало время поговорить об умножении операндов со знаком, которые представлены в формате дополнения до двух. Общая схема их умножения та же, что в в случае чисел без знака: путем многократного прибавления множимого либо набора нулей, что зависит от значения очередного разряда множителя, формируются частичные произведения.
Для начала предположим, что мы имеем положительный множитель и отрицательное множимое. Когда отрицательное множимое прибавляется к частичному произведению, по мере расширения частичного произведения значение знакового разряда должно расширяться влево. На рис. 6.6, например, 5-разрядное множимое со знаком, -13, умножается на +11, вследствие чего получаем 10-разрядное произведение — — 143. Расширение знака множимого выделено полужирным шрифтом.
Описанная схема может использоваться и для отрицательного множимого, если в ней обеспечено расширение знака частичных произведений. Если множитель отрицателен, простейшее решение состоит в формировании дополнений до двух множимого и множителя и в последующем умножении их как положительных чисел. Это возможно благодаря тому, что при дополнении обоих операндов не меняется ни значение, ни знак произведения. В следующем разделе вы познакомитесь с еще одной технологией, алгоритмом Бугла, которад позволяет одинаково обрабатывать положительные и отрицательные множители.
0 1 1 (-13) О 1 1 (+11) О 1 1 1 1 0 1 0 х 0 1 Полужирным шрифтом выделено расширение анака множимого О 1 1 1 1 1 1 0 О 0 1 0 0 0 О 1 0 1 0 0 0 0 0 0 1 1 0 0 1 О 1 1 1 О О О 1 (-143) Рис. 8.8. Расширение знака отрицательного множимого увеличивалось по мере выдвижения множителя из регистра О, В результате этого сдвига очередной разряд множителя д; оказывается в позиции 15В регистра О, которая отвечает за формирование сигнала А/ХА, равного до на первом цикле, г)~ на втором и т. д.
При атом уже использованный бит регистра Я уничтожается сдвигом. Перенос из сумматора равен крайнему слева разряду РР(1 + 1), должен быть сохранен в триггере С и сдвинут вправо вместе с содержимым регистров А и О, После выполнения и циклов старшие разряды произведения оказываются в регистре А, а младшие — в регистре О, На рис. 6.7, б показан процесс выполнения таким умножителем примера, приведенного на рис. 6.7, а.
Из приведенных схем видно, что для реализации команды умножения требуется гораздо болыпе времени, чем для выполнения команды сложения. Существует несколько технологий ускорения операции умножения; некоторые из ннх обсуждаются в следующих разделах. 6.4.1. Алгоритм Буга В результате работы алгоритма Бута генерируется 2н-разрядное произведение.
При выполнении этой операции дополнения до двух как положительных, так и отрицательных и-разрядных операндов обрабатываются одинаковым образом. Чтобы лучше понять суть алгоритма Буга, рассмотрим операцию умножения с положительным множителем, содержащим один блок единиц: 0011110. Для получения произведения можно, как и в стандартной процедуре, сложить четыре значения множимого, сдвинутых влево на соответствующее количество разрядов.
Однако число необходимых операций сократится, если множитель представлен в виде разности двух чисел: 0100000 (32) — 0000010 (2) 00!1!10 (30) Таким образом, для получения произведения можно сложить произведение множимого на 2 и дополнение до двух произведения множимого на 2!. Описывать алгоритм удобнее, если представить множитель в виде 0 +1000 -10. 0 1 О 1 1 О 1 0 О+1ч-1е1ч-1 О 0 О 0 0 О 0 О 0 1 0 1 1 О 1 О 1 О 1 1 О 1 О 1 О 1 1 О 1 0 1 О 1 1 О 1 О О 0 О О О 0 О 0 О 0 О О 0 О 0 0 1 О 1 О 1 О О О 1 1 О О 1 О 1 1 О 1 О+1 О О 0-1 О О О О О Дополнение до двух множимото О 0 0 О О О 1 О 1 0 1 0 О Рис. 6.9.
Обычная схема О 1 1 О умножения и алгоритм Буга О О О О О О 1 1 1 1 1 1 О 0 О О О 0 О О О О О 0 О О О О О О О О О 1 О 1 О О О О О О О О О О 1 О 1 О О 0 0 О О 0 О 0 0 0 О 0 1 0 1 0 0 6.4. Умножение чисел со знаком 419 420 Глава 6. АриФметика О О 1 О 1 1 О О 1 1 1 О 1 О 1 1 ΠΠΠΠ— 1 +1 -1 +1 О -1 О О О е1 -1 е1 О -1 О е1 Рис. В.то.
Преобразование множителя в алгоритме Буга О О О О О (+13) х О О О О О ( — 8) О 1 1 О 1 О -1+1 — 1 О О О О О О О О О О О 1 1 1 1 1 О О 1 1 О О О О 1 1 О 1 1 1 1 О О 1 1 О О О О О О 1 1 1 О 1 1 О О 1 О (-78) Рис. В.11. Алгоритм Бута для отрицательного множителя Давайте докажем, что алгоритм Буга корректно работает и при умножении отрицательньтх чисел. Для этого мы можем воспользоваться следующим свойством представления отрицательных чисел в системе дополнения до двух.
Если крайний слева нуль отрицательного числа Х находится в разряде л: Х - 11... 1Охь !... хе то значение Х можно представить так: Ц(Х)- — 2 '+х! тн2 +...+хох2 Правильность этого выражения )г(Х) подтверждается следующим: если представить значение Х как сумму двух чисел 11 ... 100000 ... 0 + 00... 00хь,... хв Х = 11...
1Ох! 1... хз Если рассматривать общий случай, в алгоритме Буга множитель сканируется справа налево. При переходе от 0 до 1 к частичному произведению добавляется множимое, сдвинутое влево на соответствующее количество разрядов и умноженное на — 1, а при переходе от 1 до 0 — произведение сдвинутого множимого и +1. На рис. 6.9 приведены примеры использования обычного алгоритма умножения и алгоритма Буга. Действие алгоритма Бута распространяется на любое количество блоков единиц в множителе, в том числе его можно применить в ситуации, когда блоком считается лишь одна единица.
На рис. 6.10 предлагается еще один пример преобразования множителя. Если младший бит множителя равен 1, можно считать, что справа от него находится подразумеваемый О. Алгоритм Буга подходит и для отрицательных множителей, о чем свидетельствует рис. 6.11. 6.4. Умножение чисел со знаком 421 Рис. 6.12. Таблица преобразования множителя в алгоритме Буга 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Худший вариант е1 -1 е1 -1 в1 -1 +1 -1 в1 -1 е1 -1 в1 -1 в1 -1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 0 0 Обычный вариант 0 -1 0 0 ч-1 -1 ч.1 0 -1 ч.1 0 0 0 -1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 ч.1 0 0 0 0 -1 0 0 0 в1 0 0 -1 Лучший вариант Рио.
6.13. Множители, преобразованные согласно алгоритму Буга то верхним числом будет — 2ь' в формате дополнения до двух. Преобразованный множитель представляет собой второе число, к которому в позиции 1г ч- 1 добавляется -1. Например, множитель 110110 преобразуется в 0 -1 ч-1 0 -1 О. Общая схема преобразования множителя в алгоритме Буга представлена на рис. 6.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
