Файл: 351-400.pdf

3 7 6 Глава 7. Операционные устройства вычислительных машин

Ускорение целочисленного деления

Следует отметить, что операция деления предоставляет не слишком много путей

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

- замена делителя обратной величиной, с последующим ее умножением на делимое;

-

 сокращение времени вычисления частичных остатков в традиционных мето-

дах деления (с восстановлением или без восстановления остатка) за счет уско-
рения операций суммирования (вычитания);

- сокращение времени вычисления за счет уменьшения количества операций сум-

мирования (вычитания) при расчете Ч0;

- вычисление частного в избыточной системе счисления.

За исключением первого из перечисленных подходов все прочие фактически

являются модификациями традиционного способа деления.

Замена деления умножением

на обратную величину

В предыдущем разделе было показано, что операцию умножения можно произво-

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

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

 D

 умножением на

В этом случае проблема сводится к эффективному вычислению 1

/D.

 Обычно за-

дача решается одним из двух методов: с помощью ряда Тейлора или метода Нью-
тона-Рафсона. В обоих случаях основное время расходуется на умножение,

поэтому рассматриваемый метод ускорения деления имеет смысл при наличии бы-
стрых схем умножения.

При реализации первого метода делитель

 D

 представляется в виде:

 D -

 1 +

 X.

Тогда для двоичного представления

 D

 можно записать:

Метод был использован в модели 91 вычислительной машины IBM 360 для

вычисления 32-разрядной величины

 1/D.

 Возможные значения сомножителей

в правой части выражения извлекались из таблицы емкостью 28 байт, хранящей-
ся в памяти. Операция вычисления 1

/D

 требует шести умножений.

Вычисление величины 1

/D

 методом Ньютона-Рафсона сводится к нахожде-

нию корня уравнения

то есть

 Х- 1/D.

 Решение может быть получено с привлечением рекуррентного

соотношения: •. Количество итераций определяется требуемой
точностью вычисления

 1/D.

 Реализация метода для n-разрядных чисел требует

2 int(log

2

n) - 1 операций умножения.

Ускорение целочисленного деления  3 7 7

В общем, замена операции деления на умножение более характерна для чисел

с плавающей запятой.

Ускорение вычисления частичных остатков

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

нием операций сложения (вычитания). Способы достижения этой цели ничем не

отличаются от тех, что применяются, например, при выполнении умножения. Это

различные приемы для убыстрения распространения переноса, матричные схемы

сложения и т. п. В частности, для вычисления частичных остатков может быть при-

менена матричная схема, показанная на рис. 7.53.

Рис. 7.53. Матричное устройство деления для алгоритма без восстановления остатка

Представленная схема реализует алгоритм деления без восстановления остат-

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

ния. Таким образом, матричное исполнение деления нельзя считать очень эффек-

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

Алгоритм SRT

В основе третьей группы методов ускорения операции деления, согласно приве-

денной выше классификации, лежит так называемый алгоритм SRT [77,184,214].

Свое название алгоритм получил по фамилиям авторов (Sweeney, Robertson, To-
cher), разработавших его независимо друг от друга приблизительно в одно и то же

3 7 8 Глава 7. Операционные устройства вычислительных машин

время. Этот алгоритм представляет собой модификацию деления без восстановле-
ния остатка. В стандартной процедуре на каждом шаге помимо сдвига частичного

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

Алгоритм был ориентирован на операции над мантиссами чисел с плавающей

запятой и опирается на то обстоятельство, что мантиссы в таких числах нормали-
зованы. Впервые SRT-алгоритм был реализован в модели 91 вычислительной ма-
шины IBM 360. В настоящее время он широко применяется в блоках обработки
чисел с плавающей запятой, в частности в микропроцессорах фирмы Intel.

Сначала рассмотрим алгоритм применительно к положительным целым чис-

лам. Делимое представляется (2n + 1)-разрядным числом, а делитель — «-разряд-

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

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

 k

 предшествующих

нулей реализуется за счет сдвига делителя влево на

 к

 разрядов. На аналогичное

число разрядов влево сдвигается и делимое. Далее выполняются

 п

 итераций, в ко-

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

Обратим внимание на то, что частное представляется в системе счисления, от-

личной от двоичной. Это означает, что цифры частного могут иметь больше, чем
два значения 0 и 1. В рассматриваемом случае—1,0,1.

По завершении всех

 п

 итераций, если последний остаток отрицателен, выпол-

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

Последний момент в алгоритме — преобразование частного из системы {-1,0,1}

в систему {0,1}, то есть в обычную двоичную систему.

На практике это выливается в следующую процедуру (при объяснении будем

ссылаться на схему деления без восстановления остатка, приведенную на рис. 7.50).
Делимое и делитель, представленные в дополнительном коде, размещаются в ре-
гистре делимого (РДМ) и делителя (РДТ) соответственно. Дальнейшие действия
можно описать следующим образом.

1. Если в делителе

 D

 имеются

 k

 предшествующих нулей (при

 D

 > 0) или предше-

жимого РДМ и РДТ влево на

 k

 разрядов.

2. Для i от 0 до

 п

 - 1:

Ускорение целочисленного деления  3 7 9

D если три старших цифры частичного остатка в РДМ совпадают, то

 q

t

 = О

и производится сдвиг содержимого РДМ на один разряд влево;

• если три старших цифры частичного остатка в РДМ не совпадают, а сам Ч0

отрицателен, то q

i

  - 1 , делается сдвиг содержимого РДМ на один разряд

влево и к Ч0 прибавляется делитель;

D если три старших цифры частичного остатка в РДМ не совпадают, а сам Ч0

положителен, то

 q

t

, - 1, выполняется сдвиг содержимого РДМ на разряд влево

и из Ч0 вычитается делитель.

3. Если после завершения пункта 2 остаток отрицателен, то производится кор-

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

4. Остаток сдвигается вправо на

 k

 разрядов.

Описанную процедуру иллюстрирует пример, приведенный на рис. 7.54.

Рис. 7.54. Пример деления целых чисел по алгоритму SRT

На первом шаге для удаления предшествующих нулей делитель сдвигается на

два разряда влево. Аналогично поступают и с  4 0 , который вначале совпадает с де-
лимым. Далее выполняется процедура, описанная выше в пункте 2. Операция вы-
читания

 D

 обеспечивается прибавлением делителя с противоположным знаком.

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

 D.

 Одновременно частное уменьшается на единицу (эта

операция показана в системе {-1,0,1}, в которой представлено частное). Наконец,

3 6 0 Глава 7. Операционные устройства вычислительных машин

на последнем шаге форма представления частного меняется, переходят к представ-
лению в стандартной двоичной системе.

В стандартном алгоритме деления без восстановления остатка помимо сдвига

в каждой итерации выполняется операция сложения или вычитания. В варианте

SRT, в зависимости от кодов операндов в отдельных итерациях, достаточно толь-

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

данным, в среднем число сложений и вычитаний при использовании этого алго-

ритма сокращается в 2,67 раза.

Деление в избыточных системах счисления

Наиболее распространенные методы ускорения операции деления основаны на

применении алгоритмов, где частное представляется в системе счисления, отлич-
ной от двоичной. Это означает, что цифры частного могут иметь больше, чем два

значения, например {-1,0,1}, как это было в алгоритме умножения Бута, или {-2,

-1,0,1,2}. В таких системах одно и то же число может быть записано несколькими

способами, из-за чего системы называют избыточными. Очередная цифра частного
в избыточной системе счисления, в зависимости от базы этой системы, соответ-

ствует двум или более цифрам в двоичном представлении частного, и для нужного

количества двоичных цифр частного и остатка требуется меньше итераций. В то

же время реализация такого подхода ведет к усложнению аппаратуры делителя,

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

выигрыш в быстродействии оказывается решающим моментом. Так, в микропро-

цессорах Pentium при делении мантисс чисел с плавающей запятой используется

алгоритм SRT с базой 4, то есть частное сначала вычисляется с использованием

цифр -2,  - 1 , 0, 1, 2 с последующим преобразованием результата к стандартному

двоичному представлению. В этом варианте выбор очередной цифры частного про-

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

секцию определяют четыре старшие цифры делителя (после его нормализации).

Входом в секцию служат шесть старших цифр частичного остатка. Ч0 в каждой
итерации сдвигается не на один, а на два разряда, то есть число итераций сокраща-

ется вдвое. Известны варианты делителей, где берется еще большее основание си-
стемы счисления, в частности 8 и 16. В этом случае логика работы устройства су-
щественно усложняется.

Операционные устройства

с плавающей запятой ,

Операции над числами в формате с плавающей запятой (ПЗ) имеют существен-
ные отличия от аналогичных операций целочисленной арифметики, поэтому их

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

и целочисленное ОПУ, операционное устройство для чисел в формате ПЗ как ми-