Представление информации в ЭВМ

Как и в предыдущих случаях, выполним вычисление 1213=156. После выполнения преобразований в двоичную систему счисления получаем:

0001100 множимое

0001101 множитель

0000000 СЧП

00001100 сдвиг А на разряд вправо, т.к. разряд b_i=0

000001100 сдвиг А на разряд вправо, т.к. разряд b_i=0

0000001100 сдвиг А на разряд вправо, т.к. разряд b_i=0

0000000 + СЧП

0000001100 СЧП

00000001100 сдвиг А на разряд вправо

0000001100 СЧП

00000100100 СЧП

000000001100 сдвиг А на разряд вправо

0000000001100 сдвиг А на вправо, т.к. разряд b_i=0

00000100100

0000010011100 СЧП 156.

2.5 Умножение чисел со знаком

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

Наиболее очевидная мысль -- получить абсолютные значения операндов и перемножить их как числа без знака. Справедливость такого решения видна из примера, приведенного на рис. 3.2 (показан процесс умножения чисел +13 и +10).

Рис. 3.2. Пример умножения

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

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

2.5.a Множимое произвольного знака

Пример для положительных сомножителей (А > 0, В > 0) был рассмотрен выше, в случае же отрицательного множимого процедура умножения протекает аналогично (рис. 3.3), но с учетом сделанного выше замечания об арифметическом сдвиге СЧП.



Рис. 3.3. Пример умножения с сомножителями разного знака

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

2.5.b Множимое произвольного знака. Множитель отрицательный

Так как множитель отрицателен, он записывается в дополнительном коде; [В]_Д = 2ⁿ-|В|, и в цифровых разрядах кода будет представлено число 2^n-1-|В|. При типовом умножении (как в случае В > 0) получим

.

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

Рис. 3.4. Пример умножения положительного множимого на отрицательный множитель



Рис. 3.5. Пример умножения отрицательного множимого на отрицательный множитель

Процесс умножения, представленный на рис. 3.4 и 3.5, протекает аналогично описанным в п/п 3.5 и 3.5.1, за исключением последнего этапа, где необходимо проводить коррекцию. Для коррекции необходимо вычесть избыточный член, которым является множимое.

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

В примере, показанном на рис. 3.5, исходное множимое отрицательное, поэтому при коррекции при вычитании образуется положительный знак, так как -(-13) по правилам арифметики дает положительный знак. Следовательно, необходимо прибавить число 0.1101. В результате сложения с псевдопроизведением получаем требуемое произведение.

2.5.c Умножение целых чисел и правильных дробей

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

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

Как видно, младший разряд произведения целых чисел, имеющий вес 2⁰, размещается в позиции двойного слова, соответствующей весу 2¹. Таким образом, для правильного расположения произведения в разрядной сетке двойного слова необходим дополнительный сдвиг вправо. Такой сдвиг можно учесть как в аппаратуре умножителя, так и программным способом.

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

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

2.6 Методы ускорения операции умножения

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

Логические подходы к убыстрению умножения можно подразделить на две группы:

1) методы, позволяющие уменьшить количество сложений в ходе умножения;

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

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

2.6.a Алгоритм Бута

В основе алгоритма Бута [7,9] лежит следующее соотношение, характерное для последовательностей двоичных цифр:

, (3.4)

где т и k -- номера крайних разрядов в группе из последовательных единиц. Например, 011110 = 2⁵ -2¹. Это означает, что при наличии в множителе групп из нескольких единиц (комбинаций вида 011,110), последовательное добавление к СЧП множимого с нарастающим весом (от 2^k до 2^m) можно заменить вычитанием из СЧП множимого с весом 2^k и прибавлением к СЧП множимого с весом 2^m+1.

Как видно, алгоритм предполагает три операции: сдвиг, сложение и вычитание. Помимо сокращения числа сложений (вычитаний), у алгоритма есть еще одно достоинство -- он в равной степени применим к числам без знака и со знаком.

Алгоритм Бута сводится к перекодированию множителя из системы (0, 1) в избыточную систему (-1,0,1), из-за чего его часто называют перекодированием Бута (Booth recoding). В записи множителя в новой системе: 1 означает добавление множимого к сумме частичных произведений, -1 - вычитание множимого и 0 не предполагает никаких действий. Во всех случаях после очередной итерации производится сдвиг множимого влево или суммы частичных произведений вправо. Реализация алгоритма предполагает последовательный в направлении справа налево анализ пар разрядов множителя - текущего b_i и предшествующего b_i-1 (b, b_i-1). Для младшего разряда множителя (i = 0) считается, что предшествующий разряд равен 0, то есть имеет место пара b₀0. На каждом шаге i (i = 0,1,..., п-1) анализируется текущая комбинация b,b_i-1.

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

Комбинация 01 соответствует завершению цепочки единиц, и здесь множимое прибавляется к СЧП.

Комбинация 00 свидетельствует об отсутствии цепочки единиц, а 11 -- о нахождении внутри такой цепочки. В обоих случаях никакие арифметические операции не производятся.

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

Описанную процедуру рассмотрим на примерах (используется вариант со сдвигом множимого влево). В приведенных примерах операция вычитания, как это принято в реальных умножителях, выполняется путем сложения с множителем, взятым с противоположным знаком и представленным в дополнительном коде. Для удлинения кода до нужного числа разрядов в дополнительные позиции слева заносится значение знакового разряда.

Пример: 01100011 = 00010010 (в десятичном виде 63= 18). После перекодирования Бута множитель (0,0,1,1) приобретает вид (0,1,0,-1).

Вначале сумма частичных произведений принимается равной нулю: 00000000. Полагается, что младшему разряду множителя предшествовал 0. Дальнейший процесс поясняет рис. 3.7.

Рис. 3.7. Умножение (63) в соответствии с алгоритмом Бута

Пример: В двоичной системе провести умножение чисел 11000011=11110100 или в десятичной записи -43=-12. Процесс вычисления проиллюстрируем на рис. 3.8.

Рис. 3.8. Умножение (-43) в соответствии с алгоритмом Бута

Процесс умножения, представленного на рис. рис. 3.7 происходит следующим образом. Анализ разрядов множителя начинается с младшего разряда, первая, встречающаяся комбинация в множителе является 10, поэтому производится вычитание множимого из суммы частичных произведений, после этого появляется цепочка единиц, поэтому никаких действий не производится. Следующей появляется комбинация 01, поэтому происходит прибавление множимого к сумме частных произведений. На последнем этапе появляется комбинация 00, поэтому никаких действий не происходит. В результате получается искомое произведение.

Умножение чисел, показанных на рис. 3.8 происходит аналогично умножению, показанному на рис. 3.7. Первоначально появляется комбинация 10 и происходит вычитание множимого из суммы частных произведений, затем следует цепь единиц и не производится никаких действий, после этого цепочка единиц заканчивается и производится прибавление множимого к последнему варианту суммы частных произведений. Последней остается комбинация нулей и поэтому не производится никаких действий. Последний вариант суммы частных произведений есть требуемое произведение. На рисунках представлены конечные результаты после выполнения всех промежуточных вычислений.

При наиболее благоприятном сочетании цифр множителя количество суммирований равно n/2, где п -- число разрядов множителя.

2.6.b Модифицированный алгоритм Бута

На практике большее распространение получила модификация алгоритма Бута, где количество операций сложения при любом сочетании единиц и нулей в множителе всегда равно п/2. В модифицированном алгоритме производится перекодировка цифр множителя из стандартной двоичной системы (0,1) в избыточную систему (-2,-1,0,1,2), где каждое число представляет собой коэффициент, на который умножается множимое перед добавлением к СЧП. Одновременно анализируются три разряда множителя b_i+1b_ib_-i (два текущих и старший разряд из предыдущей тройки) и, в зависимости от комбинации 0 и 1 в этих разрядах, выполняется прибавление или вычитание множимого, прибавление или вычитание удвоенного множимого, либо никакие действия не производятся (табл. 3.2).

Таблица 3.2

Логика модифицированного алгоритма Бута

хi+1	хi	xi-1	Код (-2-1 0 1 2)	Выполняемые действия
0	0	0	0	Не выполнять никаких действий
0	0	1	1	Прибавить к СЧП множимое
0	1	0	1	Прибавить к СЧП множимое
0	1	1	2	Прибавить к СЧП удвоенное множимое
1	0	0	-2	Вычесть из СЧП удвоенное множимое
1	0	1	-1	Вычесть из СЧП удвоенное множимое
1	1	0	-1	Вычесть из СЧП удвоенное множимое
1	1	1	0	Не выполнять никаких действий

Пример вычисления произведения 011001101110 = 011000111110 (в десятичном виде 25(-18)=-450) показан на рис. 3.9.

Рис. 3.9. Пример умножения (18 (-25)) в соответствии с модифицированным алгоритмом Бута

На рисунке 3.9 представлены примеры операций без представления перевода из ПК в ДК (алгоритм требует проведения операций вычитания множимого и необходим перевод в ДК). Первоначально производится вычитание из СЧП удвоенного произведения множимого (разряды множителя равны 100), после этого не происходит никаких действий, так как разряды множителя равны 111 и на последнем шаге снова происходит вычитание из СЧП удвоенного произведения множимого (разряды множителя равны 101). Как видно из примера, ускорение операции умножения достижимо за счет логического анализ разрядов множителя и сокращения количества операций суммирования, что широко используется для сокращения времени операции умножения при проектировании различных вычислительных устройств.

2.6.c Алгоритм Лемана

Еще большее сокращение количества сложений может дать модификация, предложенная м. Леманом [8]. Здесь, даже при наименее благоприятном сочетании цифр множителя, количество операций сложения не превышает величины п/2, а в среднем же оно составляет n/3. Суть модификации заключается в следующем:

· если две группы нулей разделены единицей, стоящей в k-й позиции, то вместо вычитания в k-й позиции и сложения в (k+1)-й позиции достаточно выполнить только сложение в k-й позиции;

· если две группы единиц разделены нулем, стоящим в k-й позиции, то вместо сложения в k-й позиции и вычитания в (k+1)-й позиции достаточно выполнить только вычитание в k-й позиции.

Из второй группы логических методов остановимся на умножении с обработкой за шаг двух разрядов множителя (IBM 360/370). Анализ множителя начинается с младших разрядов. В зависимости от входящей двухразрядной комбинации предусматриваются следующие действия:

· 00 ? ростой сдвиг на два разряда вправо суммы частичных произведений (СЧП);

· 01 ? к СЧП прибавляется одинарное множимое, после чего СЧП сдвигается на 2 разряда вправо;

· 10 ? к СЧП прибавляется удвоенное множимое, и СЧП сдвигается на 2 разряда вправо;

· 11 ? из СЧП вычитается одинарное множимое, и СЧП сдвигается на 2 разряда вправо. Полученный результат должен быть скорректирован на следующем шаге, что фиксируется в специальном триггере признака коррекции.

Так как в случае пары 11 из СЧП вычитается одинарное множимое вместо прибавления утроенного, то для корректировки результата к СЧП перед выполнением сдвига надо было бы прибавить учетверенное множимое. Но после сдвига на два разряда вправо СЧП уменьшается в четыре раза, так что на следующем шаге достаточно добавить одинарное множимое. Это учитывается при обработке следующей пары разрядов множителя: путем обработки пары 00 как 01, пары 01 - как 10, 10 -- как 11, а 11 -- как 00. В последних двух случаях фиксируется признак коррекции (табл. 3.3).

Таблица 3.3

Формирование признака коррекции

Пара разрядов множителя	+1 из предыдущей пары	+1 в следующую пару	Знак действия	Кратность множимому
00	0	0		0
01	0	0	+	1
10	0	0	+	2
11	0	1	-	1
00	1	0	+	1
01	1	0	+	2
10	1	1	-	1
11	1	1	+	0

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

2.6.d Умножение чисел в D-кодах

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

Пример. Умножить на сумматоре прямого кода (код D₁) числа

Решение: При умножении используются сумматор прямого кода для кода D₁ на три тетрады и регистры на две тетрады (табл. 3.4). СЧП на первом шаге алгоритма обнуляется. В приведенном примере при анализе младшей тетрады (0011) выполнено три прибавления множимого к СЧП. Затем при появлении в результате вычитания нуля производятся сдвиги СЧП и множителя на 4 разряда вправо.

Таблица 3.4

Пример операции умножения чисел в D-кодах

СЧП	Регистр В	Примечание
0000 0000 0000 1000 0110 0000 1000 0110 1000 0110 0001 0111 0010 1000 0110 0010 0101 1000 0000 0010 0101 1000 0110 0001 0001 0001 1000 0110 0001 1001 0111 1000 0110 0010 1000 0011 0000 0010 1000	0011 0011 1 0010 1 0001 1 0000 1000 0011 1 0010 1 0001 1 0000 0011 1000	Анализ младшей тетрады множителя. Результат на каждом шаге суммирования СЧП и множимого представлен после проведения коррекции Конец анализа младшей тетрады. Сдвиг на четыре разряда Анализ следующей за младшей тетрады множителя Конец анализа младшей тетрады. Сдвиг на четыре разряда

Если сомножители имеют по п десятичных разрядов, то в регистре множимого должно быть п разрядов (тетрад) справа от запятой, а в регистре СЧП должно быть п основных разрядов, одна тетрада переполнений и один (п+1)-й дополнительный десятичный разряд, который предназначен для округления результата. При необходимости сохранить все 2п разрядов произведения справа от регистра СЧП должен быть еще сдвиговый регистр для младших разрядов произведения. Регистр множителя должен иметь п тетрад справа от запятой. Причем, если младшая тетрада этого регистра выполнена в виде реверсивного счетчика, (т.е. счетчика, который может прибавлять или вычитать единицу), то операцию умножения можно ускорить в среднем почти в 2 раза. В этом случае необходимо иметь специальный разряд для записи 1, если при суммировании в счетчике-тетраде появится код 10₁₀.

Такой состав оборудования объясняется следующим образом. Если очередная цифра множителя, находящаяся в младшей тетраде регистра множителя, равна или меньше 5₁₀, то производится многократное прибавление множимого к СЧП. При каждом суммировании множимого вычитается 1 из счетчика. Такие действия выполняются до тех пор, пока на счетчике не появится код нуля. Если же очередная цифра множителя равна или больше 6₁₀, то производится многократное вычитание (сложение в дополнительном D-коде) множимого из СЧП. При каждом вычитании множимого к содержимому счетчика прибавляется 1. Вычитания продолжаются до тех пор, пока в счетчике не появится код 10₁₀, при этом в специальный разряд записывается 1.

Вторая тетрада множителя при этом приписывается на место младшей тетрады. Затем производится анализ второй тетрады множителя путем вычитания единицы по алгоритму приведенному выше. После сдвигов СЧП и множителя вправо на 4 разряда на этапе анализа второй тетрады для приведенного примера нет больше тетрад множителя, которые необходимо анализировать. В результате использования алгоритма умножения получен результат равный 0, 0000 0010 1000 0011 1000 (+2838₁₀). Знак результата определяется с использованием логической функции «сумма по модулю 2».

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

При двоично-десятичном представлении чисел удвоение числа означает сдвиг влево, а деление на 2 - сдвиг вправо, причем так как сдвиги производятся над двоичными кодами, требуется коррекция тетрад на каждом шаге. Корректирующие поправки определяются для каждого D-кода. Коррекция выполнятся тогда, когда происходит сдвиг единицы из крайнего разряда данной тетрады в соседнюю тетраду. Для кода D₁ корректирующая поправка равна +0110 для тетрад множимого и -0011 (или +1101) для тетрад множителя.

Пример. Умножить ускоренным способом (1) на сумматоре прямого кода числа (табл. 3.5):

На примере, представленном в табл. 3.5 приведена операция умножения числа -86 на -33, записанных потетрадно в двоичном коде. Здесь в колонке B показан множитель, то есть число -33, в колонке А записано множимое, то есть число -86, колонка С иллюстрирует процесс накопления произведения в СЧП. В примере показаны числа после требуемых коррекций. На первом шаге множитель отрицательный (33), следовательно, его необходимо добавить к СЧП. После этого производится сдвиг множителя на разряд вправо, а множимого - на разряд влево, при этом в множителе происходит межтетрадный перенос, в младшей тетераде множимого появляется запрещенная комбинация (число 1100), а во второй - произошел межтетрадный перенос. Следовательно разряды А и В требуют коррекции, младшую тетраду В следует скорректировать на +13 с блокировкой межтетрадного переноса, а тетрады А на +0110. После коррекции число В положительно, поэтому добавления множимого к С не происходит, а производится очередная операция сдвигов множимого и множителя. На каждом шаге производится анализ необходимости коррекции в тетрадах множимого и множителя, и добавления скорректированного множимого к С. В С в случае необходимости необходимо производить коррекции на +0110. Операция сдвигов прекращается, когда тетрада множителя станет равной 0001, при этом происходит последнее добавления А к С (значение 0001 является нечетным).

Таблица 3.5

Пример ускоренной операции умножения

В	А	С	Примечание
0011 0011 0001 1001 1101 0001 0110 0000 1011 1101 0000 1000 0000 0100 0000 0010 0000 0001	0000 1000 0110 0001 0000 1100 0110 0110 0001 0111 0010 0010 1110 0100 0110 . 0011 0100 0100 0110 1000 1000 1101 0001 0000 0110 0110 0110 0001 0011 0111 0110 0010 0100 1110 1100 0110 0110 0010 0111 0101 0010	0000 0000 1000 0110 0010 0111 0101 0010 0010 0111 1101 1000 0110 . 0010 1000 0011 1000	Сдвиг Поправки В - четное Сдвиг Поправки В - четное Сдвиг В - четное Сдвиг Поправки В - четное Сдвиг Поправки В - нечетное Поправка

2.6.d Аппаратные методы ускорения умножения

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

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

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

Наконец, третья возможность ускорения операции умножения заключается в параллельном вычислении всех частичных произведений. Если рассмотреть общую схему умножения (рис. 3.10), то нетрудно заметить, что отдельные разряды ЧП представляют собой произведения вида a_ib_j, то есть произведение определенного бита множимого на определенный бит множителя. Это позволяет вычислить все биты частичных произведений одновременно, с помощью n² схем И. При перемножении чисел в дополнительном коде отдельные разряды ЧП могут иметь вид или. Тогда элементы И заменяются элементами, реализующими соответствующую логическую функцию.

Рис. 3.10. Схема перемножения n-разрядных чисел без знака

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

· к параллельному вычислению частичных произведений;

· к сокращению количества операций сложения;

· к уменьшению времени распространения переносов при суммировании частичных произведений.

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

Параллельное вычисление ЧП имеет место практически во всех рассматриваемых ниже схемах умножения. Различия проявляются в основном в способе суммирования полученных частичных произведений, и с этих позиций используемые схемы умножения можно подразделить на матричные и с древовидной структурой [9]. В обоих вариантах суммирование осуществляется с помощью массива взаимосвязанных одноразрядных сумматоров. В матричных умножителях сумматоры организованы в виде матрицы, а в древовидных они реализуются в виде дерева того или иного типа.

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

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

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

2.7 Выполнение операции деления

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

Рис. 3.11. Общая схема операции деления

Задача сводится к вычислению частного Q и остатка S:

, . (3.5)

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

Операция выполняется за п итераций и может быть описана следующим образом:

(3.6)

(3.7)

После п итераций получается

. (3.8)

Частное от деления 2n-разрядного числа на n-разрядное может содержать более, чем п разрядов. В этом случае возникает переполнение, из-за чего перед выполнением деления необходима проверка условия

. (3.9)

Из выражения следует, что переполнения не будет, если число, содержащееся в старших п разрядах делимого, меньше делителя.

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

Реализовать деление можно двумя основными способами:

1) с неподвижным делимым и сдвигаемым вправо делителем;

2) с неподвижным делителем и сдвигаемым влево делимым.

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

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

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

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

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

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

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

5) пункты 2-4 последовательно выполняются для получения всех цифр модуля частного.

На рисунке 3.12 показан процесс деления с восстановлением остатка (здесь число 41 делится на 7).



Рис. 3.12 Пример деления с восстановлением остатка

На первом шаге алгоритма деления производится операция сдвига делимого на один разряд влево (рис. 3.12), при этом в освобождающийся разряд записывается ноль. После этого происходит вычитания из сдвинутого делимого числа разрядов делителя. Затем анализируется старший разряд частичного остатка. Если он равен 1, то есть число меньше нуля, то в разряд частного записывается 0, если - 0 (число больше нуля), то в частное записываем 1. В нашем случае он равен 1, поэтому в частное записываем ноль и производим восстановление остатка с помощью добавления делителя. Результат суммирования сдвигаем на разряд влево. На этом первый шаг деления закончен и для получения очередной цифры частного необходимо снова вычесть разряды делителя. В примере на рис. 3.12 результат вычитания больше нуля (старший разряд равен 0), поэтому в частное записываем 1. операцию необходимо продолжить до получения количества разрядов, равных количеству разрядов делителя. В итоге получаем значение частного равное 0101 (5₁₀) и в остатке 0110.

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

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

2) частичный остаток удваивается путем сдвига на один разряд влево, при этом в освобождающийся при сдвиге младший разряд ЧО заносится очередная цифра частного;

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

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

5) пп. 2-4 последовательно выполняются для получения всех цифр модуля частного.

Как видим, пп. 1, 2, 5 полностью совпадают с соответствующими пунктами предыдущего алгоритма деления.

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

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

Рис. 3.13. Пример деления без восстановления остатка

2.7.a Деление меньшего числа на большее с восстановлением остатков

Данный вид операции деления аналогично описанному выше проще всего выполнять в прямом коде. Знак частного при делении определяется как сумма по mod2 знаковых цифр делимого и делителя, и присваивается частному в конце операции деления.

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

Цифры частного определяются последовательно начиная со старшего разряда. Допустим, что в результате выполнения i циклов получены старшие i разрядов частного Y_i. В следующем -м цикле будет получено значение -го разряда частного. Исходными данными для этого цикла являются текущее значение частного Y_i и значение текущего остатка R_i.

Цифра может иметь одно из двух значений: 1 или 0.

Если , то

,

т.е. в частном записывается 0 при условии

Если , то

,

т.е. цифра частного равна 1, если выполняется условие

или .

Т.к. всегда выполняется одно из приведенных условий, то для определения текущей цифры частного достаточно проверить одно из них. Обычно проверяют первое. Очередной остаток перед началом следующего шага всегда является положительным. Для проверки правой части неравенства сравним разность (2R_i-B) с нулем. Если эта разность окажется отрицательной, то в (i+1) разряд частного записываем 0 и для подготовки исходных данных для (i+2) цикла определим R_i+1 следующим образом:

Если разность (2R_i-B) окажется положительной, то запишем в i+1 разряд частного 1, а в качестве исходного значения для (i+2)-го цикла используем вычисленную разность

.

Исходными данными явл. Y₀=0

Правило деления с восстановлением остатков формулируется следующим образом.

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

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

Рассмотрим пример операции деления с восстановлением остатков числа 5 на число 6 (рис. 3.14) с точностью до 5 значащих разрядов. То сеть необходимо 5:6=0.8(3) или в двоичном виде 0.0101:0.0110.

Рис. 3.14 Пример деления с восстановлением остатков меньшего числа на большее

В примере на рис. 3.14 не показаны промежуточные операции перевода отрицательных чисел в обратные либо дополнительные коды, так как это было показано в п. 3.2 настоящего пособия.

В результате операции деления числа 5 на число 6 получаем результат 0.11010. Данный результат является приближенным, а для перевода данного кода в десятичный эквивалент необходимо умножить каждый разряд числа на соответствующую степень двойки с учетом того, число является дробным. Например, старший разряд числа следует умножить на 2^-1, следующий разряд - на 2^-2 и т.д. до конца двоичного числа. В результате получаем число 0,8125. Т.е. результат вычислений правильный с учетом того, что деление выполнялось с точностью до 5 значащих разрядов.

2.7.b Деление меньшего числа на большее без восстановления остатков

Рассмотренный в 3.10 процесс деления с восстановлением остатков является аритмичным процессом с переменным числом шагов.

Операцию можно упростить и получить каждую цифру за два шага.

Если в предыдущем пункте остаток R_i<0, то в п. 3.10 необходимо было бы выполнить следующие операции:

1) восстановление остатка

2) сдвиг восстановленного остатка влево

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

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

Результат в данном случае отличается от действительного на величину |+B|. Поэтому в качестве второго шага необходимо произвести коррекцию результата на эту величину:

т.е. в результате получаем требуемую величину последующего остатка за 2 шага.

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

Рассмотрим пример деления двух чисел таких же как и в п. 3.10, то есть разделим 5 на 6. аналогично частное равно 0.8(3) или в двоичном виде 0.0101:0.0110 (рис. 3.15).

Рис. 3.15 Деления без восстановления остатка меньшего числа на большее

В результате операции деления получили результат аналогичный полученному в п. 3.10 - 0.11010. Аналогично в приведенном примере на рис. 3.15 не оказан перевод отрицательных чисел в дополнительный и обратный код.

2.7.c Деление чисел со знаком

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

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

Так как делимое и делитель не обязательно имеют одинаковые знаки, то действия с частичным остатком (прибавление или вычитание делителя) зависят от знаков остатка и делителя (табл. 3.4).

· если знак остатка совпадает со знаком делителя, то очередная цифра частного - 1, иначе - 0;

· если Z > 0 и D < 0, частное необходимо увеличить на 1;

· если Z < 0 и D > 0, то при ненулевом остатке от деления частное нужно увеличить на единицу;

· если Z < 0 и D < 0, то при нулевом остатке от деления частное нужно увеличить на единицу.

Таблица 3.4.

Операция, выполняемая в очередной итерации деления

Знак остатка	Знак делителя	Действие
+	+	Вычитание делителя
+	-	Прибавление делителя
-	+	Прибавление делителя
-	-	Вычитание делителя

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

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

Наиболее распространенные методы ускорения операции деления основаны на применении алгоритмов, где частное представляется в системе счисления, отличной от двоичной. Это означает, что цифры частного могут иметь больше, чем два значения, например {-1,0,1}, как это было в алгоритме умножения Бута, или {-2,-1,0,1,2}. В таких системах одно и то же число может быть записано несколькими способами, из-за чего системы называют избыточными. Очередная цифра частного в избыточной системе счисления, в зависимости от базы этой системы, соответствует двум или более цифрам в двоичном представлении частного, и для нужного количества двоичных цифр частного и остатка требуется меньше итераций. В то же время реализация такого подхода ведет к усложнению аппаратуры делителя, в частности, надстраивается логика определения операции, выполняемой в очередной итерации. Для этой цели в состав устройства деления включается специальная память, хранящая таблицу, определяющую необходимые действия в зависимости от текущей комбинации цифр в частичном остатке и делителе. Тем не менее выигрыш в быстродействии оказывается решающим моментом. Так, в микропроцессорах Pentium при делении мантисс чисел с плавающей запятой используется алгоритм SRT с базой 4, то есть частное сначала вычисляется с использованием цифр -2, -1, 0, 1, 2 с последующим преобразованием результата к стандартному двоичному представлению. В этом варианте выбор очередной цифры частного производится с помощью таблицы, состоящей из отдельных секций. Конкретную секцию определяют четыре старшие цифры делителя (после его нормализации). Входом в секцию служат шесть старших цифр частичного остатка. ЧО в каждой итерации сдвигается не на один, а на два разряда, то есть число итераций сокращается вдвое. Известны варианты делителей, где берется еще большее основание системы счисления, в частности 8 и 16. В этом случае логика работы устройства существенно усложняется.

2.7.e Замена деления умножением на обратную величину

Операцию деления на D можно заменить умножением на

, (3.10)

где D - это делитель

В этом случае проблема сводится к эффективному вычислению 1/D. Обычно задача решается одним из двух методов: с помощью ряда Тейлора или метода Ньютона-Рафсона [9]. В обоих случаях основное время расходуется на умножение, поэтому рассматриваемый метод ускорения деления имеет смысл при наличии быстрых схем умножения.

При реализации первого метода делитель D представляется в виде: D = 1 + X. Тогда для двоичного представления D можно записать:

Метод был использован в модели 91 вычислительной машины IBM 360 для вычисления 32-разрядной величины 1/D. Возможные значения сомножителей в правой части выражения извлекались из таблицы емкостью 28 байт, хранящейся в памяти. Операция вычисления 1/D требует шести умножений.

Вычисление величины 1/D методом Ньютона-Рафсона сводится к нахождению корня уравнения

(3.11)

то есть Х= 1/D. Решение может быть получено с привлечением рекуррентного соотношения X_i+t = Х_i (2 -X_iD). Количество итераций определяется требуемой точностью вычисления 1/D. Реализация метода для n-разрядных чисел требует 2int(log₂n)-1 операций умножения.

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

2.7.f Ускорение операции деления

В основе методов ускорения операции деления лежит так называемый алгоритм SRT [11,12]. Свое название алгоритм получил по фамилиям авторов (Sweney, Robertson, Tocher), разработавших его независимо друг от друга приблизительно в одно и то же время. Этот алгоритм представляет собой модификацию деления без восстановления остатка. В стандартной процедуре на каждом шаге помимо сдвига частичного остатка производится прибавление либо вычитание делителя. В SRT-алгоритме сдвиг частичных остатков (ЧО) также имеется в каждой итерации, однако сложение или вычитание, в зависимости от получающегося ЧО, на отдельных шагах может не выполняться, что, естественно, позитивно влияет на быстродействие деления.

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

Сначала рассмотрим алгоритм применительно к положительным целым числам. Делимое представляется (2п+1)-разрядным числом, а делитель - n-разрядным. Процедура деления начинается с удаления в делителе всех нулей, предшествующих старшей единице, то есть с операции, аналогичной нормализации мантиссы в числах с плавающей запятой. Будем условно называть эту операцию нормализацией. Исключение k предшествующих нулей реализуется за счет сдвига делителя влево на k разрядов. На аналогичное число разрядов влево сдвигается и делимое. Далее выполняются п итераций, в которых вычисляются цифры частного и частичные остатки. Действия, выполняемые на i-й итерации, можно описать следующим образом:

 (3.12)

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

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

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

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

1) если в делителе D имеются k предшествующих нулей (при D>0) или предшествующих единиц (при D<0), то производится предварительный сдвиг содержимого РДМ и РДТ влево на k разрядов;

2) для i от 0 до п-1:

· если три старших цифры частичного остатка в РДМ совпадают, то q_i=0 и производится сдвиг содержимого РДМ на один разряд влево;

· если три старших цифры частичного остатка в РДМ не совпадают, а сам ЧО отрицателен, то q_i = -1, выполняется сдвиг содержимого РДМ на один разряд влево и к ЧО прибавляется делитель;

· если три старших цифры частичного остатка в РДМ не совпадают, а сам ЧО положителен, то q_i = 1, выполняется сдвиг содержимого РДМ на разряд влево и из ЧО вычитается делитель;

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

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

Рассмотрим пример реализации данного алгоритма (рис. 3.16).