Лекции по дисциплине «Теория вычислительных процессов» (стр. 4 )

В ЭВМ последних выпусков для ускорения умножения используется шестнадцатиричная система, т. е. одновременно анализируются 4 разряда.

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

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

Умножение чисел с плавающей запятой

Если заданы А=а 2m и В=b 2m2 в нормальной форме, то их произведение составит AB=ab 2m1+m2

Следовательно, умножение нормализованных чисел состоит из следующих этапов:

1) определение знака произведения путем сложения по mod2 знаковых цифр мантисс сомножителей;

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

3) умножение модулей мантисс сомножителей по правилам умножения чисел с фиксированной запятой;

4) нормализация и округление мантиссы результата. Денормализация мантиссы возможна только на один разряд вправо. Для устранения путем сдвига мантиссы на один разряд слева и вычитание единицы на один разряд влево и вычитание единицы из порядка результата.

5) присвоение знака результату.

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

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

Округление мантиссы результата производится следующим образом. Если мантисса результата получилась без нарушения нормализации, то округление производится обычно добавлением единицы b(n+1) разряд СЧП. Если мантисса произведения денормализована вправо, то при 2n разрядном результате вначале производится нормализация, а затем округление, а при (n+1) разрядном результате вначале производится округление, а затем нормализация. Единица округления добавляется в (n+2) разряд только при наличии в нем 1.

Способы ускорения деления

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

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

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

2) для остатка Ri-1 справедливо:

0£Ri-1<R.

Теперь Ri-1 сдвинуть на два разряда влево, то следующую пару цифр частного и остаток можно определить по следующим правилам:

	Частное	Ri
22Ri-1<B	00	4Ri-1
B£22Ri-1<2B	01	4Ri-1-B
2B£22Ri-1<3B	10	4Ri-1-2B
3B£22Ri-1	11	4Ri-1-3B

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

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

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

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

Деление чисел с плавающей запятой

Если числа А и В заданы в нормальной форме, то их частное: Y=A:B=(a:b)2m1-m2. Поэтому операция деления выполняется в пять этапов:

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

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

3) определение порядка частного путем вычитания порядка делителя из порядка делимого;

4) нормализация результата и его округление;

5) Присвоение знака мантиссе результата.

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

2-1£|a|<|-2n

Тогда наименьшая и наибольшая возможные величины мантиссы частного равны:

|цmin|2-1>2-1; |ymax|1-2-n=2-2-(n+1)<2

-2-n 2-1

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

При выполнении третьего этапа порядок частного может оказаться больше допустимого, т. е. произойдет переполнение разрядной сетки. Может быть так же получен порядок частного, который меньше допустимого. Если на втором этапе вычислено частное |y|>1, то на четвертом этапе при сдвиге частного вправо его порядок должен быть увеличен на единицу. При этом становится окончательно ясно:

1) возникло ли переполнение разрядной сетки порядка;

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

Умножение чисел, заданных в ДК

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

Рассмотрим 4 возможных случая:

1) А>0, B>0. Сразу получаем истинное значение положительного произведения:

[А]д[В]д=[АВ]д=АВ

2) А>0, B<0. Получаем псевдопроизведение

|[A]д||[B]д=|А|(1-|В|)=|А|-|А||В|

|[AB]д|=1-|A||B|

т. е. требуется коррекция псевдорезультата на величину D=1-(А), т. е. на величину дополнения модуля множимого до 1.

3) А<0, B>0

|[AB]д|=(1-|А|)|В|=|В|-|А||В|

|[AB]д|=1-|А||В|, т. е. требуется коррекция псевдорезультата на величину D=1-|В|, т. е. на величину дополнение множителя до 1.

4) А<0, B<0

|[A]д|[B]д|=(1-|A|)(1-|B|)=1-|A|-|B|+|A||B|

Псевдорезультат требует коррекции на величину D|А|+|В|, т. к. лишняя единица размещается в знаковом разряде и может быть просто заменена знаком произведения.

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

Коррекцию псевдорезультата для отрицательного множителя можно выполнить при умножении множимого на знаковую единицу множителя, рассматривая ее как отрицательную, т. е. вместо суммирования множимого в этом цикле умножения нужно выполнить вычитание или же суммирование [-A]д. Ввиду того, что в этом цикле прибавляется 2-|А| вместо 1-|А|, то сразу же формируется и правильная знаковая цифра результата, т. к. в силу исходного сочетания знаков он должен быть отрицательным и представлен в ДК. Таким образом обеспечивается коррекция и величины результата, и его знака.

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

[А]дВ=[А]дb12-1+...+[A]дbn2-n

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

Если оба сомножителя отрицательны, то коррекция +|А|+|В| может быть получена объединением рассмотренных способов введения коррекций. При этом получается правильный результат со своим знаком.