Жмакин А.П. Архитектура ЭВМ (2006), страница 10

□ А' = —модули чисел;

□ — перенос из знакового разряда;

□ — ситуации переполнения в дополни­тельном коде.

В алгоритме рис. 3.22 можно отметить один недостаток. При выполнении вычитания (/ = 1) необходимо получить дополнение второго операнда:

В' := В' +1, что является арифметической операцией и требует времени, дос­таточного для прохождения переноса по всем разрядам числа. Для исключе­ния дополнительной арифметической операции можно в первой операторной

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

В':= В';

C:=A + B + f.

3.8. Алгоритмы умножения

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

а модуль произведения равен произведению модулей сомножителей.

Обозначим А', В', С — модули сомножителей и произведения соответст­венно. Тогда

Выражение (3.26) определяет процесс формирования произведения путем вычисления частичных сумм и суммы частичных произведений. Напомним, что by — старший разряд множителя, а b_п — младший. Вычисляя непосред­ственно по формуле (3.26), следует на каждом шаге:

1. Проанализировать очередную цифру множителя b_t. Если b, = 1, то оче­редная частичная сумма равна А, и она добавляется к накопленной ранее сумме частичных произведений S (на первом шаге S = 0), иначе добав­ления не производится.

2. Осуществить правый сдвиг частичного произведения S на один разряд.

Умножение S-2~^l соответствует делению на 2, что в двоичной системе счисления равносильно сдвигу числа на один разряд вправо.

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

Очевидно, число шагов при использовании приведенного выше метода равно разрядности модуля множителя. Алгоритм умножения чисел, представлен­ных в прямом коде, приведен на рис. 3.23.

В изображенном на рис. 3.23 алгоритме, в отличие от алгоритмов сло­жения/вычитания, значение OV — 0 устанавливается безусловно. Действительно, А и В — дробные числа; очевидно при |A|<1 и |B|<1 всегда |А∙B|<1.

В результате вычисления по формуле (3.26) получается произведение разряд­ностью 2п. Если рассматривать сомножители как дроби, то младшие п раз­рядов можно просто отбросить (округление с недостатком) или округлить до п -разрядного модуля по правилам округления.

Очевидно, из выражения (3.26) легко получить

С' = А'В' =

= (...(0 + ∙ A'- )-2 + ∙А'-Ь₂)-2 + ...+ (3.27)

+ ∙А'∙ )∙2 + ∙А'∙ )∙2,

что позволяет производить умножение, начиная со старших разрядов множи­теля. При этом сдвиг суммы частичных произведений осуществляется влево на один разряд, чему соответствует умножение двоичного числа на 2.

3.8.1.Умножение в дополнительном коде

Если числа поступают на обработку уже представленные в дополнительном коде, то для умножения их можно перевести в прямой код или умножать сра­зу в дополнительном коде. В последнем случае в умножении участвуют и знаковые разряды сомножителей, причем знак произведения получается в том же цикле, что и разряды модуля произведения. Однако в некоторых слу­чаях требуется коррекция предварительного результата. Мы не будем рас­сматривать здесь случаи умножения в дополнительном коде. Любознатель­ным рекомендуем соответствующую литературу, например [11].

3.8.2.Методы ускорения умножения

Методы ускорения умножения принято делить [8, 11] на аппаратные и логи­ческие. Как те, так и другие требуют дополнительных затрат оборудования. При использовании аппаратных методов дополнительные затраты оборудо­вания прямо пропорциональны числу разрядов в операндах. Эти методы вы­зывают усложнение схемы операционного автомата АЛУ.

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

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

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

Здесь частичные произведения формируются на схемах «-разрядных конъ-юнкторов одновременно и подаются на входы п -входового сумматора, при­чем в сумматоре за счет соответствующей коммутации цепей осуществ­ляются сдвиги частичных произведений (как при выполнении умножения на бумаге "в столбик"). На выходе сумматора получается 2и -разрядное произ­ведение.

Метод табличного умножения (рис. 3.25) позволяет получить произведение за один такт при условии, что вся таблица умножения (результаты умноже­ния всевозможных пар и-разрядных сомножителей!) будет размещена в па­мяти. Очевидно, для этого понадобится запоминающее устройство объемом

2²ⁿ 2n -разрядных слов (точно таким же способом можно выполнять и дру­гие "длинные" операции — деление, вычисление функций). Так, для органи­зации 8-разрядного умножителя потребуется память объемом 2¹⁶ х 16 бит =128 Кбайт, что для современного уровня развития интегральной технологии не кажется чрезмерным.

Однако для 16-разрядного АЛУ умножитель "потянет" уже на 2³² х 32 бит =16 Гбайт! Что касается современных 32-разрядных процессоров, то к расче­ту потребности в памяти для таких умножителей даже страшно приступать.

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

Рассмотрим этот способ умножения подробнее. Пусть п — четное. Тогда каждый из двух сомножителей можно представить конкатенацией двух по­лей одинаковой разрядности n/2: А = A_h A_l, В = B_hB_l. В этом случае произ­ведение можно представить следующим выражением:

AxB = A_l ∙ B_l+2^n/2 ∙A_h-B_l+2^n/2 ∙ А_l ∙B_h + 2ⁿ • A_h ■ B_h

Таким образом, располагая, например, таблицей умножения 8x8, можно получить произведение двух 16-разрядных сомножителей, сложив (с соответ­ствующим сдвигом) всего 4 слагаемых. Проиллюстрируем этот метод на про­стом примере.

Пусть требуется перемножать 4-разрядные числа без знака. Построим табли­цу умножения 2x2 (при рассмотрении примера не будем включать в нее па­ры сомножителей, когда один из них равен нулю, а так же пары сомножите­лей, симметричные уже включенным) — рис. 3.26.

Пример 3.22

Выполним умножение 6x10 = 60 или в двоичном коде 01.10x10.10 = 00111100. Из таблицы получаем частичные произведения: А₁хВ₁ =10x10 = 0100, A,xB_h =10x10 = 0100, A_h хВ, =01x10 = 0010, A_hxB_h =01x10 = 0010.

Теперь сложим частичные произведения, предварительно сдвинув их в соот­ветствии с (3.28). Результат — на рис. 3.27.

Пример 3.23

Выполним умножение 7x11 = 77 или в двоичном коде 01.11x10.11 = 01001101.

Из таблицы получаем частичные произведения: A_t х5, = 1 lxl 1 = 1001, Л, xB_h =11x10 = 0110, A_hxB, =01x11 = 0011, A_hxB_h =01x01 = 0001.

Теперь сложим частичные произведения, предварительно сдвинув их в соот­ветствии с (3.28). Результат — на рис. 3.28.

Среди логических наиболее распространены в настоящее время методы, по­зволяющие за один шаг умножения обработать несколько разрядов множите­ля. Рассмотрим один из способов умножения на два разряда множителя, на­чиная с его младших разрядов. В зависимости от результата анализа пары разрядов множителя предусматриваются следующие действия (табл. 3.3).

Таким образом, для умножения сразу на два разряда множителя доста­точно:

□ при 00 просто произвести сдвиг на два разряда;

□ при 01 прибавить к сумме частичных произведений множимое и про­извести сдвиг на два разряда;

□ при 10 прибавить к сумме частичных произведений удвоенное мно­жимое и произвести сдвиг на два разряда;

□ при 11 вычесть из суммы частичных произведений множимое (или до­бавить обратный (дополнительный) код множимого), произвести сдвиг на два разряда и добавить 1 к следующей (старшей) паре цифр множителя.

При классическом методе умножения двоичных я -разрядных чисел согласно выражению (3.26) потребуется п сдвигов суммы частичных произведений и п/2 (в среднем) сложений множимого с суммой частичных произведений. Один из методов ускорения операции умножения — анализ сразу двух разря­дов множителя. Это позволит получить результат, применяя п/2 сдвигов и (в среднем) Зи/8 сложений/вычитаний.

3.9. Алгоритмы деления

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