4.4. МЕТОДЫ УСКОРЕНИЯ ОПЕРАЦИИ УМНОЖЕНИЯ

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

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

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

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

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

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

В среднем количество сложений при этом сокращается вдвое.

Можно уменьшить и среднее, и максимальное количество суммирований при использовании как прямых, так и инверсных передач множимого в сумматор. Здесь учитывается то обстоятельство, что время умножения значительно сокращается, если при наличии в разрядах множителя цепочки нулей подряд производить его сдвиг сразу на несколько разрядов. Для этого видоизменяют код множителя с целью представления его с меньшим количеством разрядов, содержащих единицу. Этот код требует как прямых, так и инверсных передач множимого в сумматор. Например, группу единиц в множителе можно преобразовать в группу т. е. перейти к системе с цифрами 1,0, 1.

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

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

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

Следует отметить, что при умножении старшими разрядами применяются несколько другие правила определения оптимального множителя. И в том, и в другом случае в среднем на каждую операцию сложения выполняется сдвиг на 2,9 разряда, если схема рассчитана на сдвиг не более чем на 6 разрядов одновременно.

Таблица 4.1

В пределе среднее число сложений-вычитаний, приходящееся на один разряд множителя, равно . Это наилучший результат, которого можно достичь при использовании логических методов.

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

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

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

Тогда для младшей пары разрядов при умножении с младших разрядов возможны следующие комбинации единиц и нулей в разрядах

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

данной пару разрядов. С учетом этого действия при умножении выполняются в соответствии с табл. 4.1.

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

Например, множителю 0,100111 соответствует преобразованный множитель 0,101001.

Пример.

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

Умножение выполняется за 3 такта вместо

Таким образом» ускорение умножения достигается за счет того, что: при комбинации 11 два сложения заменяются одним вычитанием, которое эквивалентно сложению благодаря использованию инверсных кодов;

добавление 1 в соседнюю старшую группу множителя производится одновременно с вычитанием множимого и, следовательно, не увеличивает время умножения.

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

в первом такте

во втором такте после сдвига содержимого сумматора на 2 разряда вправо Если , то Будем исходить из худшего варианта, когда во всех тактах умножения выполняются операции Тогда в сумматоре будет получена последняя сумма следующего вида:

Таблица 4.2

При любом А сумма . Следовательно, при данном способе умножения сумматор должен иметь три знаковых разряда.

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

Следует отметить, что объем оборудования АУ при умножении на два разряда несколько увеличивается по сравнению с работающим без ускорения.

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

Этот способ может быть реализован, например, путем предварительного формирования таблицы значений занесения этой таблицы в соответствующие регистры и подключения их выходов ко входу сумматора. Получить таблицу можно следующим образом. На сумматор передается а затем во втором такте добавляется Результат сложения передается в первый регистр таблицы и остается на сумматоре. В третьем такте путем прибавления на сумматоре формируется результат и передается во второй регистр таблицы, в четвертом такте получается Значения множимого формируются при передаче на сумматор

Таблица 4.3

множимого с регистра А прямым или инверсным кодом со сдвигом соответственно на 1,2 и 3 разряда влево. Значения множимого формируются при передаче значения из первого регистра таблицы прямым или инверсным кодом со сдвигом на один разряд влево.

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

Следует отметить, что при реализации данного способа сумматор должен содержать 5 знаковых разрядов, а регистры таблицы но 4 знаковых разряда.

Умножение с запоминанием промежуточных переносов

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