Основы информатики_Савельев А.Я_Учебник_2001

6 4 Ускорение операции деления

Если теперь остаток сдвинуть на два разряда, то 2^ Л^_^. Тогда следующую пару цифр частного можно найти из условий, представленных в таблице 6.5.

Изложенный алгоритм деления может быть упрощен, если каждую па­ ру цифр частного определять, исходя из анализа нескольких старших раз­ рядов делителя В и сдвинутого остатка 2^ Д_|. При этом если старшие раз­ ряды остатка 2^ Д_| совпадают со старшими разрядами групп, то предполагается, что 2" Д_| принадлежит к области с наибольшим значени­

Гогда коррекция остатка осуществляется следующим образом; если раньше проверялось условие JB < 2" Д_, <(J + \)В, где J = О, I, 2, 3 , то те­ перь проверяется эквивалентное ему условие

и-^)В<2\А,_,-В)<и~^)В. (6.6) Можно сформулировать правила, представленные в таблице 6.6.

Таблица 6.6

Но этим правилам строятся указанные алгоритмы выполнения опера­ ции деления.

151

6Выполнение операций деления чисел на двоичных сумматорах

6.5.Параллельные методы деления с использованием

итерагнвиых структур

Как npaBHjiO, при выполнении операции деления тратится один такто­ вый цикл для получения одной двоичной цифры частного. Параллельные делители практически невозможно реализовать, используя классический прием оггределения цифры частного: вычитанием делителя из TCKyrriero ос­ татка делимого. Вместе с тем наличие быстродействующи?^ пар<1лле;гьных умножителей (см. гл. 5) позволяет создавать !гараллельные алгори1мы де­ ления с использованием этих умножителей. Можно реализовать алгоритм деления, используя обратную величину делителя и замену операции деле­ ния операцией умножения. При этом обра1ная величина делителя для всею диапазона значений хранится в ПЗУ. Емкость ПЗУ зависит от разрядности машинного слова (см. табл. 6.7) .

\ а б л !( ца 6 7

Рассмотрим возможность реализации операции де;!енил с использова­ нием итеративных структур на примере устройства, предложепгюю и рабо­ те М. Каина, В. К- Галахера «Итеративное устройство для ускоренною дво­ ичного деления». Здесь приняты следующие обозначения:

делимое — А- AQ- А^А2...Л^^\

делитель — D - DQ- D^D2 ...D/^; остаток — Н = R^^' R^R2 ...R/^;

частное — Q = QirQiQ2--QN •

Предполагается, что все операнды г!оложительные, нормализованные дроби. В итерационной матрице деления (ИМД) исгюльзуегся алгоритм деления без восстановления остатка, описанный ранее, но с двумя суигествеиными из­

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

Мейзер С. Элпшан Н- «Быс1ролейс1В>ю!пее >'С1ройство деления ЛЯЙ сиециалнитронапиы\ ИС различно!"» ижиачсния» М.'')лск1ромика. № 14. 1989 С 29 ^S

152

6 5 Параллельные методы деления с использованием итеративных структур

Первое изменение заключается в том, что промежуточный остаток R не формируется в каждом ряду матрт1цы, а представляется в виде двух двоич­ ных векгоров S и С, которые, будучи сложенными, дают настоящее значе­ ние промежуточного остатка в данном ряду матрицы. Второе изменение состоит в применении дополнительной схемы, для того чтобы по виду век­ торов S и С определять, произойдет ли перенос в знаковый разряд проме­ жуточного остатка. Эта схема облегчает определение знака промежуточно­ го остатка, очередного разряда частного и сигнала управления (прибавлять или отнимать делитель) для следующего ряда матрицы.

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

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

На таком сумматоре задержка сигнала определяется только одной логиче­ ской ячейкой и не зависит от длины операндов. Быстродействие схемы опре­ деления переноса в знаковый разряд, выборка делителя или его дополнения, задержка на одну ячейку при суммировании — 0С1ювные факторы, опредеflflFoume время, необходимое для формирования одного разряда частного.

Определение переноса в знаковый разряд промежуточного остатка проводшся по формуле

где О^ =Л',С', — порождающая функция; Pi-S^+Cj — накапливающая фугп<ция.

^1ля с;гучая Л' разрядов имеем

а= ,V|C'| + (5, + С, )SjCj + (S, + С, )(Sj •+ Cj) X

>= ,v,c, + •. • + (.f, + С,)... ( V 2 + c«-2)V i C » - i •

Для описания алгоритма деления ИМД можно использовать обозначе­ ния, приведенные в гл. 5. Векторы S и С — это векторы поразрядной суммы и переноса соответственно, получающиеся на сумматоре типа 3 в 2 (полный сумматор).

Алгоритм работы ИМД выглядит следующим образом: Цикл для / — от О до N.

Ill а г 1. Формирование двух новых векторов промежуточного остатка: если й_| = 1, то S, С := S + С - D ;

если й_| = 0 , T o 5 , C : = S + C + D .

153

6 Выпачнеиив onepaiiuu деления чисел на двоичных сумматорах

1JJ а г 2. Определение переноса в знаковый разряд промежуточного осгатка:

Ш а г 3. Определение знака промежу'1очпого остатка:

Определение очередного разряда частного: Q, = RQ •

Шаг 4. Сдвиг векторов S и С влево: 5:= 2(5), С~2{С). Для / ^ 0 формально принимается 5 ' - Л - деление, Q_i=\ и С - 0 . Основным явля­ ется шаг !, сформированный выше, он может быть проиллюстрирован cjreдующнм образом:

С(, -CjCj-.X^^jC;^

Биты, опредепягошне f 7

Комбинация суммирования с запоминанием переносов и ускоренного определения знака промежуточного остатка обеспечивает высокое быстро­ действие алгоритма ИМД при не очень больших затратах на дополнитель­ ное оборудование.

Для ИМД, описанной выше, время деления возрастает линейно с уве­

в знаковый разряд (основание логарифма определяется максимальным ко­ эффициентом объединения по входу логических схем). Время деления в базовой матрице деления, описанной выше, растет пропорционально Л'^ из-за распространения переноса вдоль каждого ее ряда.

Для Л' = 16 ИМД работает в 2,6 раза быстрее базовой матрицы деле­ ния, но дороже ее на 22 % . Для Л' = 32 скорость ИМД в пять раз превыша­ ет скорость базовой матрицы деления и дороже ее на 25 %.

Пример 6.5. Разделить с помощью ИМД /1 = 0,1001! иа Д=0,11001 на суммаюре до­ полнительного кода.

Р е ш е н и е : |/1), =0,10011,1В], =0.11001. [В]. =1,00111;

Г/, = 5,0 + (.% + f'i ftC) + (•SI + С, %S\ + Cj )S,C, + (S, + C, )(.?j + Q )(5, + Г, )5,С^ Ответ: С, =011000.

154

с10 10 0 0

Па рис. 6.2 пр^'дставлена типовая процессорная ячейка, разработанная AipasarteM для ите,"дативных структур, используемых для устройств деле­ ния. В типовой я'ц-«е сигнал 6, прибавляется к результату суммирования

155

б Выполнение операций деления чисел на двоичных сумматорах

Общая схема делительного устройства представлена на рнс. 6.3. Основ­ ными элементами этого устройства являются одноразрядные сумматоры с ускоренным переносом (ОСУП). На рис. 6.3 величина а (делимое, имеет семь разрядов) делится на величину h (делитель, имеет четыре разряда), разряды частного q получаются на соответствующих выходах. При этом разряд частного 9, = I только тогда, когда прибавление делителя h и дополнительном коде приводит к положительному остатку, что указывается единицей переполнения из старшего значащего разряда. С другой стороны, если 9 ^ - 0 , то первоначальное значение остатка на эгом niaie восстанавливается. В устройстве деления в каждом ряду матричной структуры образуются две частичные суммы. Поэтому восстановление происходит несколько своеобразным способом. Если возникает необходимость восстановления (или любого неарифметического действия), то результат суммирования двух частичных остатков от предыдущего Hiara передается в следующий ряд как входная величина. Дополнительнь!Й код делителя образуется как обратная величина в каждом разряде дели(е;!я, чю вызывает перенос е-\ и добавление единицы в правый разряд делигеля.

Очень важна процедура определения знака остатков. Примем во вни­ мание следующее;

1) если коррекция не требуется, то среди переменных .S", С,, С, и Г^., д только одна величина может быть равна единице (если единице равна не одна величина, то это указывает на положительный знак);

6 6 Операция извлечения квадратного корня

6.6. Операция июлсчення квадратного корня

()ггераг1ия ишлечспия квадратного корня как самостоятельная операция в сис1ему коман;! ЭВМ включае1ся в случае, когда приходится относительно час!о прибегагь к ее вьнюлнению (не менее 2 % от общего числа операций). I акис сипации Moryi встречаться при создании специализированных ЭВМ .

OcHOBiibtM приемом для приближенного вычисления Квадратного кор­ мя и >nnBcpcajH.HMX ЭВМ является метод итераций, ос1юванный на использовапни формулы Иыоюна.

I h c n , V' = V J . Ч'огда F{x, у) = у^ -х==0, F'(x, у) = 2у. Считая, что

V,, =s 1 ссп, п))и0Jmжerиioe значение искомой функции, по теореме Лагранг

157

(у Bhinowemie операций деления чисел на двоичных сулгматорох

О, Ьф^ ..-^i_|Oi . Первое значение переменного делителя равно 0,01.

Пример 6.6. Извлечь квадратный корень из числа А =0.100101 на сумматоре дополни­ тельного кола.

Р е ш е н и е . См. табл. 6.9. Отвег: Я =/^ = 0.110000,

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

Задание для самоконтроля

1. Разделить заданные в прямом коле числа: а) 1/1]^р = 1,100011 и 1^]^^ = !,! 100П . б) Щпр =0,100111 и [й]„р =1.1000П,

2. Разделить заданные в обратном коде числа [А]^ = 1,011001 и [В]^ = 0.11001 методом с восстановлением остатков.

158

й= -0.111001 2', прелставленггых в форме с плавающей запятой.

8.Вочможио ли переполнение разрядной сетки при делении чисел, представленных в форме с илавакнией занятой?

9.Извлечь квадратный корень из числа /1 = 0,111 П 1 Fiaсумматоре обратного кода.

159

7. ВЫПОЛИКНИЕ ОПЕРАЦИЙ НАД ДЕСЯТИЧНЫМИ ЧИ( ЛАМИ R ЦИФРОВЫХ АВТОМА ГАХ

7.1. П|>с;11:1нн11С1111с ;ич'111И'||1Ы\ чисс! к Д-колах

Операции над дсснгичными числами (десятичная арифмоика) чпсю включаются в cociau основных команд универсальных ')RM . Кроме кчо . десятичная арифметика рсаличуетсЯ широко в члсктромных к.члькчляюрах и персональных микро'^НМ. Почгому кроме общей ии(])ормацмц о 1ичмо:)к- HociH 11рсд,сгяР1Лсиии десятичных чисел разработчику нсопхо;н1\!о nian, и ajHopHiM иынолиспия арифметических операции-

Д-коО 1()в{)ичио-ко()1/рова11И(>е iipeikantKiienue) Оеся/личпо.'о чист — такое е.Ч) прейспишлеиие. в котором ка.ждая (к'сятичиая цифра ииюражастся ик/тра^ой la двоичных симаояоп:

рядов.

Количество различных Дчсодои определяется количеством lioiMO/itiibix сочетаний ио 10 иа 16 комбинаций, которые допускает гстрада.

При о6[)азоваимн Д-кода следует исходить ит общих |рс6оияний, гтре>и>являемых к системам счисления;

р;13.аичным десятичным цифрам должны соответстуоватт, различные 1еграды,

66jn,ujafl деснгич!1ан цифра должна и'юГ>ряжа1Ься Подыион 1с1[)ад1Ч1 (если разряды !е|рады имеют вес по диоичиой системе счисления):

дли десятичшлх ци(})р ц - {a,ja-,a-,a| | и А - {P.iPiP^l^i i - свячаппых со ои!о|1!унием а t /.'- 9. дол?кцо удовлетворяться }'слоиис

Д-К(1Л!' oripmoBJirio (11 ПОЛНО! о иа:ш: