Ускорение операции умножения

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

При использовании аппаратурных методов дополнительные затраты оборудования прямо пропорциональны числу разрядов операндов. Эти методы вызывают усложнение схемы АЛУ (ОА).

При реализации логических методов ускорения умножения, дополнительные затраты оборудования не зависят от разрядности операндов. Усложняется, в основном, схема управления (УА).

В ЭВМ для ускорения умножения используется комбинация этих методов.

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

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

Наиболее простой способ ускорения – пропуск тактов суммирования в случаях, когда очередная цифра множителя равна 0.

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

Например, при умножении на два разряда множителя, в каждом цикле анализируются два разряда множителя, начиная с младших разрядов. Множитель разбивается на группы по два разряда. В зависимости от их значения возможны 4 комбинации: 00, 01, 10, 11.

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

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

При комбинации 10 производится добавление к сумме частичных произведений удвоенного множимого (сдвинутого на один разряд влево) и сумма частичных произведений и множитель сдвигаются на два разряда вправо.

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

В первых трех случаях результат получается верным, а в последнем – неправильный и требует корректировки на следующем шаге. Если следующая пара 00, то она обрабатывается как пара 01; если 01, то она обрабатывается как пара 10; если - 10, то как 11; если 11, то как 00 и фиксируется необходимость коррекции при обработке следующей пары. Признак необходимости коррекции может запоминаться в специальном триггере. Если старшая пара разрядов множителя 11 или 10 и состояние триггера коррекции 1, то к полученному произведению должно быть добавлено множимое.

Матричные методы умножения

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

ДЕЛЕНИЕ ЧИСЕЛ С ФИКСИРОВАННОЙ ТОЧКОЙ В ПРЯМОМ КОДЕ

Существуют различные методы деления . В ЭВМ находят применение в основном 2: 1) “школьный” алгоритм деления, заключающийся в том, что делитель на каждом шагу вычитается столько раз из делимого (начиная со старших разрядов), сколько это возможно для получения наименьшего положительного остатка. Это число записывается в разряд частного и?

2) Метод умножения делимого на обратную величину делителя.

В универсальных ЭВМ обычно используется разновидность “школьного” алгоритма.

Рассмотрим более подробно, как осуществляется деление в ЭВМ по данному методу если операнды представлены в прямом коде. При делении чисел А/В в ЭВМ с фикс. Точко1 необходимо соблюдать условие А<В, чтобы результат был <1 (для запятой, фиксированной через старший разряд)

Деление в 2 этапа:

1) определение знака результата: сложение по mod 2 знаковых разрядов

2) деление модулей, округление частного, присваивание знака

Алгоритм деления с восстановлением остатка.

Если деление условно считать некоторым исходным (предыдущим) сдвинутым на один разряд влево остатком, то правило машинного деления двух дробных положительных чисел можно сформулировать так:

Предыдущий остаток сдвигается влево на один разряд и из него вычитается делитель, в результате чего формируется текущий остаток; цифра, взаимообратная знаковой цифре текущего остаток, записывается в соответствующий разряд частного; если текущий положителен, то он становится предыдущим остатком для следующего шага, а данный шаг на этом заканчивается ; если же текущий остаток отрицателен, то к нему прибавляется делитель для восстановления предыдущего, сдвинутого влево остатка, который становится предыдущим остатком для следующего шага. Операции сдвига, вычитания, а в случае необходимости и восстановления повторяются до тех пор, пока в частном не получится требуемое количество значащих цифр. После этого производится округление частного. Обычно в частном формируется n+1 значащая цифра, после чего к (n+1) цифре добавляется 1 для округления частного до n цифр. Знак частного определяется суммой по mod 2 знаковых разрядов.

Основные способа деления с восстановлением остатков:

1) ацикличность процесса деления обусловленная нерегулярностью появления микрооперации восстановления остатков, что приводит к усложнению устройства управления делением

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

Попытаемся упростить операцию деления:

Пусть - предыдущий остаток

-текущий остаток

-последующий остаток

Проанализируем такой шаг деления, в котором текущий остаток оказался отрицательным и приходится делать восстановление предыдущего (сдвинутого) остатка.

Исходное условие:

В соответствии с правилом деления надо выполнить следующие микрооперации

1) восстановление предыдущего (сдвинутого влево) остатка:

2) Сдвиг восстановленного остатка влево на один разряд

3) вычитание модуля делителя из полученной кодовой комбинации

Т.о. если выполняется (1), то надо как то сразу перейти от текущего остатка R_i к последующему R_i+1.

Пусть первым действием, как и на шаге без восстановления, будет выполнение микрооперации сдвига отрицательного остатка R_i влево

Сравнивая (2) и (3) замечаем, что они отличаются только выражением для |X₂|

Если сумма то получим то что надо. На основе приведенного анализа можно сформулировать правило деления без восстановления остатков:

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

Знак частного определяется суммой mod 2 знаковых разрядов.

Деление целых чисел

Основная особенность деления целых чисел в прямом коде заключается в том, что делимое всегда берется 2n, а делитель n разрядным, В результате деления модулей операндов формируется (n-1) разрядная целая часть частного и n-разрядный остаток со своим знаком.

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

Вариант устройств деления

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

1) сдвигать остаток влево, делитель неподвижен

2) сдвигать делитель вправо, остаток неподвижен

Способ со сдвигом остатка влево

УОЦ - устр-во обращения цифр

УСЗ - устр-во схемо знака

УУД - устр-во управления делением

Способ со сдвигом остатка вправо

Основа устройств деления - сумматор и два регистра. Делимое в нулевом такте заносится в сумматор. В первом способе сумматор производит сдвиг текущего остатка влево и алгебраическое сложение его с делителем. Передача в сумматор модуля делителя (сложение) или дополнение модуля до единицы (вычитание) обеспечивается устройством управления делением, которое анализирует выталкиваемые при сдвиге из сумматора знаковые цифры остатков. Эти цифры, проходя через устройство обращения цифр (УОЦ), инвертируются (заменяются на взаимообратные) и подаются на младший разряд сдвигающего регистра частного уже как цифра частного.

Во втором способе одновременно с передачей цифры делителя в сумматор, осуществляется и сдвиг ее вправо. Здесь введено устройство съема знаков (УСЗ) остатков, т.к. нет выталкивания знаковых разрядов из сумматора.

Во втором случае сумматор и регистр делителя имеют удвоенную длину, но 2-й способ более быстродействующий.

Не нашли, что искали? Воспользуйтесь поиском по сайту: