Операционные устройства вычислительных машин (стр. 2 )

Рис. 7.21. Умножение чисел при положительном множимом и отрицательном множителе

Рассмотренные процедуры умножения чисел со знаком в принципе могут быть реализованы с помощью ранее рассмотренного устройства (см. рис. 7.16). На практике для перемножения чисел со знаком применяют иные алгоритмы. Наиболее распространенным из них является, алгоритм Бута, имеющий дополнительное преимущество, — он ускоряет процесс умножения по сравнению с рассмотренным ранее. Этот алгоритм будет рассмотрен ниже.

Рис. 7.22. Умножение чисел при отрицательном множимом и отрицательном множителе

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

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

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

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

Ускорение целочисленного умножения

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

Логические методы ускорения умножения

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

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

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

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

Рассмотрим первую группу логических методов.

Алгоритм Бута

В основе алгоритма Бута [63] лежит следующее соотношение, характерное для

последовательностей двоичных цифр:

где m и k — номера крайних разрядов в группе из последовательных единиц.

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

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

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

Комбинация 10 означает начало цепочки последовательных единиц, и в этом

случае производится вычитание множимого из СЧП.

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

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

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

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

принято в реальных умножителях, выполняется путем сложения со множителем,

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

Напомним, что для удлинения кода до нужного числа разрядов в дополнительные

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

Пример 1.0110x0011 = (в десятичном виде 6x3 = 18). После перекодирования Бута множитель (0, 0,1, 1) приобретает вид (0, 1, 0, -1).

Вначале сумма частичных произведений принимается равной нулю — ).

Полагается, что младшему разряду множителя предшествовал 0. Дальнейший процесс поясняет рис. 7.24.

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

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

На практике большее распространение получила модификация алгоритма Бута,

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

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

Пример вычисления произведения 011001 х 101 ПО = (в десятичном виде 25 х (-18) = -450) показан па рис. 7.26.

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

алгоритмом Бута

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

Еще большее сокращение количества сложений может дать модификация, пред­ложенная Леманом [151]. Здесь, даже при наименее благоприятном сочетании цифр множителя, количество операций сложения не превышает величины n/2, а в сред­нем же оно составляет n/3. Суть модификации заключается в следующем: - если две группы нулей разделены единицей, стоящей в 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. В последних двух случаях фиксируется признак коррекции.

Таблица 7.2. Формирование признака коррекции

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

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

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

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

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

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

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

Наконец, третья возможность ускорения операции умножения заключу в параллельном вычислении всех частичных произведений. Если paccмотреть общую схему умножения (рис. 7.27), то нетрудно заметить, что отдельные разряды ЧП представляют собой произведения вида aibj, то есть произведение определенного бита множимого на определенный бит множителя. Это позволяет вычислить все биты частичных произведений одновременно, с помощью п2 схем «И». При перемножении чисел в дополнительном коде отдельные разряды ЧП могут иметь вид Тогда элементы «И» заменяются

элементами, реализующими соответствующую логическую функцию.

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

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

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

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

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

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

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

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

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

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

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

Матричное умножение чисел без знака

Результат Р перемножения двух n-разрядных двоичных целых чисел А и В без зна­ка можно описать выражением

Умножение сводится к параллельному формированию битов из п n-разрядных частичных произведений с последующим их суммированием с помощью матрицы сумматоров, структура которой соответствует приведенной матрице умножения. Схема известна как умножитель Брауна. На рис. 7.28 показан такой умножитель для четырехразрядных двоичных чисел, в котором каждому столбцу в матрице умножения соответствует диагональ умножителя. Биты частичных произведений (ЧП) вида aibj формируются с помощью элементов «И». Для суммирования ЧП Применяются два вида одноразрядных сумматоров с сохранением переноса: полу­сумматоры (ПС)1 и полные сумматоры (СМ).

------

1 Полусумматоры называется одноразрядное суммирующее устройство, имеющее дна входа для слагаемыx и два входа и два выхода — выход бита суммы и выход бита переноса.

Рис. 7.28. Матричный умножитель Брауна для четырехразрядных чисел без знака

Матричный умножитель п х п содержит пг схем «И», ПС и (п2 - 2п) СМ. Если принять, что для реализации полусумматора требуются два логических элемента, а для полного сумматора — пять, то общее количество логических элементов в ум­ножителе составляет п2 + 2п + 5(п2 - 2л) = 6п2 – 8n.

Быстродействие умножителя определяется наиболее глинным маршрутом рас­пространения сигнала, который в худшем случае (пунктирная линия на рис. 7.28) включает в себя прохождение одной схемы «И», двух ПС и (2п - 4) СМ. Полагая задержки в схеме «И» и полусумматоре равными Л, а в полном сумматоре — 2Д. общую задержку в умножителе можно оценить выражением {4n - 5)Д. Чтобы со­кратить ее длительность, n-разрядный сумматор с последовательным переносом в нижней строке умножителя можно заменить более быстрым вариантом сумма­тора. Последнее, однако, не всегда желательно, поскольку это увеличивает число ис­пользуемых в умножителе логических элементов и ухудшает регулярность схемы.

В общем случае задержка в матричных умножителях пропорциональна их разрядности: 0(п).

Матричное умножение чисел в дополнительном коде

К сожалению, умножитель Брауна годится только для перемножения чисел знака. При обработке знаковых чисел отрицательные представляются дополнительным кодом, а матричные умножителя строятся по схемам, отличным от схемы Брауна. Прежде всего, напомним, что запись двоичного тела в дополнительном коде (с дополнением до 2) имеет вид '£"

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

Исходя из приведенной записи, произведение Р двух n-разрядных двоичных целых чисел А и В в дополнительном коде (значение произведения и сомножителей в дополнительном коде обозначим соответственно V(P), V{A) и V(B)) можно

Матрица умножения чисел со знаком, представленных в дополнительном коде, похожа на матрицу перемножения чисел без знаков (рис. 7.29). Отличие состоит в том, что (2n - 2) частичных произведений инвертированы, а в столбцы п и (2n - 1) добавлены единицы.

Рис. 7.29. Матрица перемножения n-разрядных чисел а дополнительном кода

Соответствующая схема матричного умножителя для четырёхразрядных чисел показана на рис. 7.30.

Здесь (2n - 2) частичных произведений инвертированы за счет замены элемен­та «И» на элементы «И-НЕ». Сумматор в младшем разряде нижнего ряда складывает 1 в столбце n с вектором сумм и переносов из предшествующей строки, реализуя при этом следующие выражения:

Инвертор в нижней строке слева обеспечивает добавление единицы, в столбец (2n-1).

Рис. 7.30. Матричный умножитель для четырехразрядных чисел в дополнительном коде

Алгоритм Бо-Вули

Несколько иная схема матричного умножителя, также обеспечивающего умноже­ние чисел в дополнительном коде, была предложена Бо и Були [61]. В алгоритме Бо-Вули произведение чисел в дополнительном коде представляется следующим соотношением:

Матрица умножения, реализующая алгоритм, приведена на рис. 7.31, а соответствующая ей схема умножителя — на рис. 7.32. . '

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

Рис. 7.31. Матрица перемножения n-разрядных чисел согласно алгоритму Бо-Вули

Рис. 7.32. Матричный умножитель для четырехразрядных чисел в дополнительном коде по схеме Бо-Вули

Алгоритм Пезариса

Еще один алгоритм для вычисления произведения чисел в дополнительном коде был предложен Пезарисом [181].

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

Рис. 7.33. Виды сумматоров, применяемых в матричном умножителе Пезариса

В сумматоре типа СМО, который фактически является обычным полным сумматором. все входные данные (x, у, z) имеют положительный вес, а результат лежит в диапазоне 0-3. Этот результат представлен двухразрядным двоичным числом cs, где с и s также присвоены положительные веса. В остальных трех типах сумматоров некоторые из сигналов имеют отрицательный вес. Схема умножений в рассматриваемом методе показана на рис. 7.34.

Рис. 7-34. Матрица перемножения n-разрядных чисел согласно алгоритму Пезариса

Здесь знак «минус» трактуется следующим образом: -1 = -2 * 1 + 1; -0 = -2 * 0 + 0. Схема умножителя, реализующего алгоритм Пезариса, приведена на рис. 7.35.

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

Древовидные умножители

Сократить задержку, свойственную матричным умножителям, удается в схемах, построенных по древовидной структуре. Если в матричных умножителях для cсуммирования п частичных произведений требуется п строк сумматоров, то в древовидных схемах количество ступеней сумматоров пропорционально Iog2n (рис. 7.3(3)-Соответственно числу ступеней суммирования сокращается и время вычисления СЧП. Хотя древовидные схемы быстрее матричных, однако при их реализации требуются дополнительные связи для объединения разрядов, имеющих одинаковый вес, из-за чего площадь, занимаемая схемой на кристалле микросхемы, может оказаться даже больше, чем в случае матричной организации сумматоров. Еще одна проблема связана с тем, что стандартное двоичное дерево не является самой эффективной древовидной иерархией, поскольку не позволяет в полной мере

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

Рис. 7.36. Суммирование частичных произведений в умножителях: а — с матричной структурой; б — со структурой двоичного дерева

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

Древовидные умножители включают в себя три ступени:

- ступень формирования битов частичных произведений, состоящую из п2 эле­ментов «И»;

- ступень сжатия частичных произведений — реализуется в виде дерева параллельных сумматоров (накопителей), служащего для сведения частичных произведений к вектору сумм и вектору переносов. Сжатие реализуется несколькими рядами сумматоров, причем каждый ряд вносит задержку, свойственна одному полному сумматору;