4. г <- и ~gd

W J

5. 99 +

9.4. Беззнаковое длинное деление

Под "длинным делением" подразумевается деление двойного слова на одинарное.

В случае 32-битовой машины это деление 64+32 => 32 с неопределенным результатом в случае переполнения (в частности, при делении на 0).

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

программирования высокого уровня доступно только деление вида 32+32 =* 32. Таким образом, разработчики компьютеров могут предпочесть обеспечить наличие только ко-

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

9.4. БЕЗЗНАКОВОЕ ДЛИННОЕ ДЕЛЕНИЕ 149

6. end

Это экономит две команды ветвления (если в компьютере имеется возможность вычисления указанных предикатов без использования ветвления). На Compaq Alpha предикаты из этого алгоритма вычисляются одной командой (CMPULE), на MIPS требуется выполнение двух команд (SLTU, XORI). На большинстве компьютеров вычисление каждого из этих предикатов требует выполнения четырех команд (трех при наличии полного набора

логических команд) путем использования выражения для xSy из раздела 2.11 с упрощениями, основанными на том, что в строке 1 известно, что rf, = 1, а в строке 5 - что rfj, = О. Это позволяет упростить выражения.

В строке 1: я></=(n&-i(n-rf))3>31

В строке 5; r>d ={r\-,{r-d))»2l

Мы можем получить код без ветвлений, если считать, что при d>2" частное должно быть равно 0. В этом случае делитель можно использовать в команде знакового деления, поскольку при неверном его расдознавании как отрицательной величины результат устанавливается равным О (что находится в корректных переделах частного - до 1). Случай большого делимого обрабатывается, как и раньше, сдвигом перед делением на одну позицию вправо и сдвигом частного на одну позицию влево. Это дает нам следующую программу (требующую вьшолнения 10 базовых RISC-команд).

1. ti-d»3l

2. ni-nSi.-t

Аппаратный алгоритм сдвига и вычитания

В качестве первой попытки выполнения длинного деления рассмотрим, как это деление реализуется аппаратно. Существует два щироко распространенных алгоритма, называемых восстанавливающим (restoring) и невосстанавливающим (nonrestoring) делением [31, sec. А-2; 14]. Оба алгоритма представляют собой алгоритмы "сдвига и вычитания". В восстанавливающей версии, показанной ниже, восстанавливающий щаг состоит в прибавлении делителя, когда вычитание дает отрицательный результат. Величины х, у и г хранятся в 32-битовых регистрах. Изначально х\\у представляет собой делимое размером в два слова, а делитель располагается в z. Для хранения переполнения при вычитании нам потребуется однобитовый регистр с. Вот как выглядит этот алгоритм, do (<-1 to 32

с II д; II у <- 2{х II у) II Сдвиг влево на один бит

с\\х{с\\х)-{тIIг) Вычигание(33 бита)

Уо-* Установка одного бита частного

if с then c*<-(c*) + (OftOz) Восстановление end

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

единиц, а остаток - величину у. В частности, 0-!-0=>2" - Item О . Охарактеризовать прочие случаи переполнения гораздо сложнее.

Было бы неплохо, если бы при ненулевом делителе алгоритм давал корректное значение частного по модулю 2 и корректное значение остатка. Однако, похоже, единственный способ добиться этого - создать регистр длиной свьипе 97 бит для представления с 11*11 у и выполнить тело цикла 64 раза, что обеспечит выполнение деления вида

62-i-32 64. Вычитание при этом остается 33-битовой операцией.

Реализовать этот алгоритм программно достаточно сложно, поскольку у больщинства компьютеров нет 33-битового регистра, который бы хранил значение с je. В листинге 9.2 приведен вариант алгоритма, который в определенной степени следует рассмотренному аппаратному алгоритму.

Листинг 9.2. Беззнаковое длинное деление, алгоритм сдвига и вычитания

unsigned divlu(unsigned х, unsigned у, unsigned z)

Деление (x у) на z int i; unsigned t;

for (i = 1; i <= 32; i++) {

t = (int)x >> 31; Bee биты = 1,

если x(31) = 1 X = (x << 1) I (y >> 31); Сдвиг xy влево у=у<<1; на один бит

if ( (X I t) >= z)

X = X - Z;

у = у + 1;

return У;

Остаток хранится в х

Переменная t используется для того, чтобы обеспечить правильное сравнение. После сдвига XI I у необходимо выполнить 33-битовое сравнение. Если первый бит х равен 1 (до выполнения сдвига), то совершенно очевидно, что интересующая нас 33-битовая величина больше, чем 32-битовый делитель. В этом случае все биты х 11 равны единице, гак что сравнение с z дает правильный результат (true). Если же первый бит х равен О, то 32-битового сравнения достаточно.

Код в листинге 9.2 требует выполнения от 321 до 358 базовых RISC-команд, в зависимости от того, насколько часто результат сравнения оказывается истинен. Если компьютер имеет команду сдвига влево двойного слова, операция сдвига может быть выполнена с помощью одной команды вместо четырех. Это позволяет снизить общее количество выполняемых команд до 225-289 (в предположении, что для управления циклом требуется выполнение двух команд на итерацию).

Если принять х=0, то алгоритм из листинга 9.2 может быть использован для реализации деления 32+32 => 32. Единственное упрощение при этом состоит в том, что переменную t можно не использовать, поскольку ее значение всегда равно 0.

Ниже приведен невосстанавливающий аппаратный алгоритм беззнакового деления. Основная идея состоит в том, что после вычитания делителя z из 33-битовой величины с II JC нет необходимости добавлять z, если результат оказался отрицательным. Вместо этого в следующей итерации достаточно выполнить сложение вместо вычитания. Это связано с тем, что добавление z (для коррекции ошибки, связанной с вычитанием z в предыдущей итерации), сдвиг влево и вычитание z эквивалентео его добавлению (2{u + z)-z = 2u + z). Преимущество данного метода в контексте аппаратной реализации

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

Делимое представляет собой двойное слово * у , а делитель - слово z. По окончании вычислений частное находится в регистре у, а остаток - в регистре х. с = 0

do to 32

if с = 0 then do

с II * IIУ <- 2{х II у) Сдвиг влево на один бит

с II д; <- (с II *)-(OuOz) Вычитание делителя end

else do

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

9.4. БЕЗЗНАКОВОЕ ДЛИННОЕ ДЕЛЕНИЕ