close

Вход

Забыли?

вход по аккаунту

?

MarkovskiiMarkSyetina

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
С. Г. Марковский, Н. В. Марковская,
Т. А. Суетина
ПАРАЛЛЕЛЬНОЕ УМНОЖЕНИЕ
В ЦВМ
Учебное пособие
Санкт-Петербург
2012
УДК 004.38(075)
ББК 32.973.2я73
М27
Рецензенты:
кандидат технических наук, доцент В. П. Попов;
доктор технических наук, профессор Е. А. Крук
М27
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Марковский, С. Г.
Параллельное умножение в ЦВМ: учеб. пособие / С. Г. Марковский, Н. В. Марковская, Т. А. Суетина. – СПб.: ГУАП, 2012. – 68 с.:
ил.
ISBN 978-5-8088-0761-7
В пособии рассмотрены аппаратные алгоритмы умножения,
широко используемые в современных цифровых вычислительных
машинах. Рассмотрены матричные и древовидные алгоритмы умножения целых чисел в ЭВМ. Приведено большое число примеров
решения представленных алгоритмов умножения.
УДК 004.38(075)
ББК 32.973.2я73
ISBN 978-5-8088-0761-7
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2012
© С. Г. Марковский, Н. В. Марковская,
Т. А. Суетина, 2012
ПРЕДИСЛОВИЕ
Операция умножения широко используется в цифровой обработке сигналов, преобразовании Фурье и при решении многих других задач. Основные алгоритмы последовательного умножения, используемые в цифровых вычислительных машинах, были подробно рассмотрены в [1]. При последовательном умножении произведение формируется за n шагов, где n – разрядность сомножителей.
На каждом шаге выполняются операции сложения и сдвига, для
реализации которых используются соответствующие схемы (единственный сумматор и регистры с организацией сдвига). Ускорить
выполнение операции умножения можно при помощи логических
методов ускорения или методов параллельного умножения.
Логические методы ускорения умножения [1] сводятся к преобразованию множителя в такую форму, чтобы число операций
сложения или вычитания при выполнении умножения было по
возможности меньшим. При этом количество дополнительного оборудования, необходимого для реализации конкретного алгоритма,
не зависит от количества разрядов в сомножителях, а ускорение достигается усложнением схемы управления при неизменной структуре арифметических цепей.
Параллельное умножение предполагает использование нескольких схем, каждая из которых реализует сложение на определенном
шаге. Операции сдвига выполняются определенным связыванием
этих схем между собой.
Методы параллельного умножения принято называть также аппаратными методами, т.к. они позволяют достичь ускорения за
счет использования дополнительных устройств обработки (дополнительной аппаратуры). Аппаратные методы ускорения умножения сводятся:
к уменьшению времени распространения переносов при суммировании частичных произведений (ЧП);
к параллельному вычислению ЧП.
Уменьшение затрат времени на распространение переносов достигается за счет представления суммы ЧП (СЧП) в форме с сохранением переноса, благодаря чему суммирование двух чисел не связано с распространением переноса вдоль всех разрядов числа.
Параллельное вычисление ЧП предполагает вычисление всех
разрядов ЧП одновременно. Отдельные разряды ЧП представляют
собой произведение одного бита множимого на один бит множителя и имеют вид aibj. Для получения всех разрядов ЧП необходимо
3
n2 элементов логического умножения. Суммирование полученных
ЧП организуется за счет массива взаимосвязанных одноразрядных
сумматоров. Организация этого массива в виде матрицы реализует
матричную схему умножения. Способ организации массива в виде
дерева характерен для древовидных умножителей.
Аппаратные методы умножения позволяют организовать конвейерную обработку, когда необходимо выполнить большое число
операций умножения подряд. При этом выполнение нескольких
операций умножения может перекрываться во времени, т. е. на
конвейере на разных стадиях могут выполняться разные операции
умножения, что позволяет существенно ускорить выполнение этих
операций.
В данном пособии рассматриваются матричные и древовидные
умножители целых беззнаковых чисел и целых чисел со знаком,
представленных в дополнительном коде. Все рассматриваемые
алгоритмы сопровождаются подробными примерами. С целью
упрощения изложения материала, все алгоритмы умножения рассматриваются для четырехразрядной двоичной сетки. При необходимости все рассуждения могут быть обобщены на, более общий,
n-разрядный случай.
В приложении 1 приведено описание программы проверки знаний студентов по матричным алгоритмам умножения. Приложение 2 содержит описание программы тестирования для древовидных алгоритмов умножения.
4
1. МАТРИЧНОЕ УМНОЖЕНИЕ ЧИСЕЛ БЕЗ ЗНАКА
Произведение двух четырехразрядных целых чисел без знака
можно представить следующим образом:
P = A  B = (a323 + a222 + a121 + a020) 
(b323 + b222 + b121 + b020) = a0b0 + (a1b0 + a0b1) 21 +
+ (a2b0 + a1b1 + a0b2) 22 + (a3b0+ a2b1+ a1b2+ a0b3) 23 +
+ (a3b1 + a2b2 + a1b3) 24 + (a3b2 + a2b3) 25 + a3b3 26,
(1)
где A = (a3 a2 a1 a0) (2), B = (b3 b2 b1 b0) (2), P = (p7 p6 p5 p4 p3 p2 p1 p0) (2).
Умножение сводится к параллельному формированию битов из
четырех четырехразрядных ЧП с последующим их суммированием при помощи матрицы сумматоров. Для формирования битов частичных произведений типа aibj используются элементы ”И”. Матрица умножения, реализующая выражение (1) представлена на
рис. 1, а матричный умножитель четырехразрядных чисел без знака – на рис. 2. Его называют умножителем Брауна. Каждому столбцу умножителя соответствует диагональ в матрице умножения.
1.1. Матрица сумматоров
В матричных умножителях суммирование осуществляется матрицей сумматоров, которая состоит из строк одноразрядных сумматоров. Для суммирования ЧП используются два вида одноразрядных сумматоров с сохранением переноса: полусумматоры (1/2С)
a 3a 2 a 1 a 0
b 3b 2 b 1 b 0
x
+
a 3b 3
p7
p6
a 3b 2
a 2b 3
a 3b 1
a 2b 2
a 1b 3
p5
p4
a 3b 0 a 2 b 0 a 1b 0 a 0b 0
a 2b 1 a 1b 1 a 0b 1
a 1b 2 a 0b 2
a 0b 3
p3
p2
p1
p0
Рис. 1. Матрица умножения
5
a3
a2
a1
a0
b0
&
&
&
&
p0
b1
&
&
1/2C
c s
&
1/2C
c s
&
1/2C
c s
p1
b2
&
&
ПС
c s
&
ПС
c s
&
ПС
c s
p2
b3
&
&
ПС
c s
&
ПС
c s
&
ПС
c s
p3
ПС
c s
p7
ПС
c s
p6
p5
1/2C
c s
p4
Рис. 2. Умножитель Брауна для 4-разрядных чисел без знака
и полные сумматоры (ПС). 1/2С представляет собой одноразрядное
суммирующее устройство, имеющее два входа для слагаемых и два
выхода – выход суммы и выход переноса. ПС в отличие от 1/2С име6
ет три входа для слагаемых. Видно, что каждая строка матрицы добавляет к сумме частичных произведений (СЧП) очередное частичное произведение. Поскольку промежуточные СЧП представлены в
избыточной форме с сохранением переноса, то вплоть до последней
строки распространения переноса не происходит.
Следует отметить, что схема на рис. 2 достаточна громоздкая.
С целью ее упрощения, в дальнейшем на схеме будем показывать
только матрицу сумматоров, а элементы “И” изображать не будем.
Кроме того, при построении матрицы сумматоров будем использовать только полные одноразрядные сумматоры. Соответственно,
полусумматоры в схеме на рис. 2 преобразуем в полные сумматоры,
добавляя на третий вход логический 0. Схема полного одноразрядного сумматора представлена на рис. 3, а матрица сумматоров для
умножителя Брауна – на рис. 4.
В схеме на рис. 3, a и b – разряды слагаемых, p – перенос из предыдущего разряда, s – разряд суммы, c – перенос в следующий разряд.
1.2. Сумматор с сохранением переноса
Сумматор с сохранением переноса (ССП) является одним из основных элементов матричного умножителя. Каждая строка матрицы сумматоров представляет собой ССП.
Рассмотрим принцип действия ССП. ПС позволяет складывать
три одноразрядных числа. При этом в n-разрядном сумматоре с
распространением переноса в качестве третьего слагаемого ПС выступает перенос, поступающий или с предыдущего n-разрядного
сумматора, или со схемы передачи переноса предыдущего ПС. Если
a
p
ПС
c
b
s
Рис. 3. Полный одноразрядный сумматор
7
a3b0
a2b0
0
ПС
a 3b2
p7
a2b3
a3b3
ПС
ПС
ПС
ПС
p6
p5
p4
ПС
ПС
a2b2
ПС
a1b3
ПС
0
a1b1
ПС
a1b2
a 0b0
0
a2b1
a 3b1
a 1b0
ПС
a0b1
ПС
a0b2
a0b3
0
p3
p2
p1
p0
Рис. 4. Матрица сумматоров
для 4-разрядного умножителя Брауна
в качестве третьего слагаемого использовать соответствующий разряд третьего n-разрядного числа и не передавать перенос в следующий ПС, то на выходе ПС формируется сумма в данном разряде
(ui) и перенос (vi+1). ССП используется не только в умножителях,
но и когда необходимо ускорить сложение более двух n-разрядных
чисел.
Рассмотрим пример сложения трех четырехразрядных чисел A,
B и C с использованием ССП.
S = A + B + C = a323 + a222 + a121 + a020 + b323 +
+b222 + b121 + b020+ c323 + c222 + c121 + c020 =
= (a3+ b3 + c3) 23 + (a2+ b2 + c2) 22 + (a1+ b1 + c1) 21 +
+(a0+ b0 + c0) 20.
(2)
Полный одноразрядный сумматор выполняет следующую операцию:
ai + bi + pi= 2vi+1 + ui,
(3)
где pi – перенос из предыдущего разряда.
8
Подставляя (3) в (2) получим:
S = (2v4+ u3)23 + (2v3+ u2)22 + (2v2+ u1)21 + (2v1+ u0)20 =
=(0+ v4)24 + (u3+ v3)23 + (u2+ v2)22 + (u1+ v1)21 + u0 =
= V + U, V = (v4v3v2v10), U = (0u3u2u1u0).
(4)
В результате ССП преобразует три четырехразрядных слагаемых A, B, C в два пятиразрядных V и U с той же суммой. Поэтому,
для такого ССП, иногда, используют обозначение ССП3–2. Схема,
реализующая (3) с использованием ССП представлена на рис. 5.
Строка ПС, обведенная на рис. 5 пунктиром, и представляет собой
ССП. Полученные на выходе ССП слагаемые V и U могут быть обработаны для вычисления окончательного результата любым сумматором с распространением переноса. Для ускорения вычислений,
в схеме на рис. 5, использован параллельный сумматор со схемой
ускоренного переноса.
Для сравнения на рис. 6 представлена схема сложения 3 чисел
без использования ССП. В этой схеме два слагаемых складываются
сумматором с последовательным распространением переноса, а результат сложения складывается с третьим слагаемым в параллельном сумматоре.
Задержка схемы сложения с использованием ССП составляет ПС + СМ, где ПС – задержка полного сумматора, а СМ – задержка схемы параллельного сумматора. В то время как, задержка
схемы с использованием обычного сумматора с распространением
переноса составляет 5ПС + СМ. Видно, что схема с использованием ССП имеет значительный выигрыш по быстродействию.
a2
a3
b2
b3
ССП
ɉɋ
0
v4
A3 B3
S5
S4
с3
ɉɋ
v3
u3
с2
S2
с1
ɉɋ
v2
u2
b0
b1
A2 B2
A1 B1
Параллельный сумматор
S3
a0
a1
ɉɋ
v1
u1
с0
u0
A0 B0
S1
S0
Рис. 5. Схема сложения трех чисел с использованием ССП
9
ССП могут использоваться для сложения более 3 чисел. На
рис. 7 показана схема сложения 6 четырехразрядных чисел на базе
четырех ССП3–2 (ССП6–2) и параллельного сумматора. На рисунa2
a3
b3
p4
0
c3
p3
u3
S4
ПС
c2
A 3 B3
ПС
S5
ПС
a0
a1
b2
u2
p2
p1
ПС
c1
S2
ПС
u1
c0
A 2 B2
A 1 B1
Параллельный сумматор
S3
b0
b1
0
u0
A 0 B0
S1
S0
Рис. 6. Схема сложения трех чисел с использованием сумматора
с распространением переноса
(1111) (1111) (1111)
4
4
4
A6
A5
A4
(1111) (1111) (1111)
4
4
4
A3
A2
A1
ССП 3–2
ССП 3–2
(11110)
(1111) 4
5
(11110 )
4
(1111)
ССП 3–2
5
6
(101000)
5
(10100)
ССП 3–2
ССП 6–2
6
(111110)
5
(11110)
Параллельный
сумматор
7
(1011010)
Рис. 7. Схема сложения шести чисел с использованием ССП
10
ке также показан результат сложения для случая, когда все числа
принимают максимальное значение, равное 15(10) или 1111(2).
1.3. Характеристики матричных умножителей
К преимуществам матричных умножителей следует отнести высокое быстродействие и регулярность их структуры, что особенно
важно при их реализации в виде интегральной микросхемы. Основной недостаток – большая площадь, занимаемая на кристалле
микросхемы, которая при увеличении n увеличивается пропорционально n2.
В общем случае при n-разрядных сомножителях матричный умножитель Брауна содержит n2 схем “И”, n(n1) полных сумматоров. Аппаратные затраты умножителя Брауна определяются как:
AБрауна = n2AИ + n (n1) AПС, где AИ – затраты схемы ”И”, AПС – затраты ПС. Аппаратные затраты можно также выразить в числе логических элементов, используемых для построения умножителя.
Подобные оценки можно найти в [2].
Быстродействие умножителя определяется наиболее длинной
цепочкой распространения сигнала, которая возникает, когда
1
0
1
0
0
0
0
1
0
ПС
p7
1
p6
0
1
ПС
0
1
1
1
0
0
0
p5
0
0
1
ПС
0
ПС
0
0
0
ПС
0
1
1
1
1
ПС
ПС
0
1
0
ПС
0
1
ПС
1
0
0
ПС
1
0
ПС
0
0
ПС
0
1
0
1
0
p4
p3
1
p2
1
p1
1
p0
Рис. 8. Пример умножителя Брауна для чисел 11 и 13
11
все n разрядов сомножителей имеют единичные значения. Для
n-разрядных сомножителей задержка умножителя Брауна составляет Брауна = И + (2n2)ПС, где И – задержка схемы ”И”,
ПС – задержка полного сумматора. В наихудшем случае, при четырехразрядных сомножителях сигнал проходит через одну схему “И” и шесть ПС (пунктирная линия на рис. 4), т. е. Брауна =
= И + 6ПС. Если последнюю строку, в умножителе на рис. 4, реализовать на сумматоре с параллельным переносом, то задержку
умножителя можно уменьшить: Брауна = И + (n1)ПС +СМ, где
СМ – задержка схемы параллельного сумматора. При четырехразрядных сомножителях: Брауна = И + 3ПС +СМ.
Пример матричного умножителя Брауна для чисел 11(10) =
= (1011)(2) и 13(10) = (1101)(2) приведен на рисунке (см. рис. 8), значение разряда суммы, формируемое полным сумматором, записано
справа в квадратной рамке. Рядом слева указано значение переноса. Результат умножения P = 143(10) = (10001111)(2).
12
2. МАТРИЧНОЕ УМНОЖЕНИЕ ЧИСЕЛ СО ЗНАКОМ
2.1. Основы умножения чисел
в дополнительном коде
Пусть A=(a3 a2 a1 a0)(2) – четырехразрядное число со знаком,
представленное в дополнительном коде, где a3  знаковый разряд.
Обозначим через A+ положительное число A (a3 = 0), а через A  отрицательное число (a3 = 1).
Имеем:
A+ = + (a2 a1a0)(2) = a020 +a121 + a222(10).
(5)
A- = -[(a2 a1 a0 ) + 1](2) =
= -[ (1 - a0 )20 + (1 - a1 )21 + (1 - a2 )22 + 1] (10) .
(6)
Преобразуем (6), раскрыв скобки в слагаемых. Тогда,
A =  [20 + 21 + 22 + 1  a020  a121  a222] =
= 23 + a0 20 +a1 21 + a2 22 = a323 + a222 +a121 + a020.
Если в выражение (5) добавить слагаемое a323, равное 0, при
a3 = 0, то получим, что A+ = A. В результате имеем выражение для
представления числа A в дополнительном коде при любом знаке
числа:
A = a323 + a222 +a121 + a020.
(7)
Пример. A = (0101)(2) = 1 · 22 + 1 = 5(10),
A = (1101)(2) = 1 · 23 + 1 · 22 + 1 = 3(10).
Рассмотрим операцию изменения знака числа A.
 A = a323  a222  a121  a020. Учитывая, что 20 + 21 + 22 + 1 =
= 23 имеем:
 A = a323  a222  a121  a020 + 20 + 21 + 22 + 1  23 =
= (1  a3)23  (1  a2)22  (1  a1)21  (1  a0)20 + 1.
Теперь сравним A и  A:
A = a323 + a222 + a121 + a020 + 0,
 A =  (1  a3)23  (1  a2)22  (1  a1)21  (1  a0)20 + 1,
- A = A + 1.
(8)
13
Вывод: Для изменения знака числа необходимо каждый разряд
числа проинвертировать (0 заменить на 1, а 1 на 0) и к младшему
разряду числа добавить 1 по правилам сложения чисел без знака.
Пример. A = (0101)(2)= 5(10), B = (1111)(2)= 1(10),
A = [(1010) + 1](2) = (1011)(2) = 5(10),
B = [(0000) + 1](2) = (0001)(2) = 1(10).
Теперь перемножим четырехразрядные числа A и B, представленные в дополнительном коде, используя выражение (7):
P = A  B = ( a323 + a222 + a121 + a020) (b323 + b222 +
+ b121 + b020) = a0b0 + (a1b0 + a0b1) 21 + (a2b0 + a1b1 + a0b2) 22 +
+ (a3b0 + a2b1 + a1b2  a0b3) 23 + (a3b1 + a2b2  a1b3) 24 +
+ (a3b2  a2b3) 25 + a3b3 26.
(9)
2.2. Матричный алгоритм умножения
в дополнительном коде
Умножитель Брауна может быть использован только для перемножения целых чисел без знака. Учитывая формулу (8) (9), произведение чисел в дополнительном коде можно записать следующим
образом:
P = A ´ B = a0 b0 + (a1b0 + a0 b1 )21 +
+(a2b0 + a1b1 + a0 b2 )22 + (a3b0 + a2b1 + a1b2 +
+a0 b3 + 2)23 + (a3b1 + a2b2 + a1b3 + 2)24 +
+(a3b2 + a2b3 + 2)25 + a3b3 26.
(10)
Принимая во внимание, что 24 + 25 + 26 = 27  24, запишем
P = A ´ B = a0 b0 + (a1b0 + a0 b1 )21 + (a2b0 + a1b1 + a0 b2 )22 +
+(a3b0 + a2b1 + a1b2 + a0 b3 )23 + (a3b1 + a2b2 + a1b3 -1)24 +
+(a3b2 + a2b3 )25 + a3b3 26 + 27.
(11)
Матрица умножения чисел в дополнительном коде согласно выражению (11) приведена на рис. 9. Отметим, что при вычислении p4
учитывалось, что вычитание единицы в одном разряде равносильно операции сложения с единицей по модулю 2.
14
a3 a2 a1 a0
b3 b2 b1 b0
x
1
a3 b 0
a2 b 0 a 1 b 0 a 0 b 0
a3 b 1
a2 b 1
a1 b 1 a 0 b 1
a3 b 2
a2 b 2
a1 b 2
a0 b 2
a2 b 3
a1 b 3
a0 b 3
p4
p3
+
1
a3 b 3
p7
p6
p5
p2
p1
p0
Рис. 9. Матрица умножения чисел в дополнительном коде
Видно, что эта матрица отличается от матрицы перемножения
чисел без знака только тем, что в ней 2n2 ЧП инвертированы, а
в столбцы с весами n и 2n1 добавлены единицы. ЧП с инверсией
реализуются на элементах ”И-НЕ”.
Добавление 1 в столбце с весом 2n1 реализуется при помощи
инвертора.
a3b0
a2b0
0
a2b1
a3b1
ПС
a3b2
a2b3
a3b3
ПС
ПС
ПС
ПС
p6
p5
p4
ПС
ПС
a2b2
ɉɋ
a1b3
ПС
a1b0
0
0
a1b1
a0b1
ПС
a1b2
ПС
a0b0
ПС
a0b2
a0b 3
1
1
p7
p3
p2
p1
p0
Рис. 10. Матричный умножитель чисел в дополнительном коде
15
0
0
1
0
0
1
1
1
ПС
0
0
1
0
ПС
1
ПС
0
0
1
ПС
0
1
1
0
ПС
0
0
1
0
1
ПС
0
0
0
ПС
0
0
ПС
0
0
ПС
0
1
0
1
1
1
ПС
0
p7
ПС
0
0
p6
1
ПС
0
0
p5
1
1
0
0
p4
1
p3
1
p2
1
p1
1
p0
Рис. 11. Пример матричного умножителя
в дополнительном коде для чисел 5 и 3
Аппаратные затраты матричного умножителя чисел в дополнительном коде определяются как: Aдоп.код = (n(n2)+2)AИ + (2n2)
AИ–НЕ + n(n1)AПС + AНЕ, где AИ  аппаратные затраты схемы ”И”,
AИ–НЕ  аппаратные затраты схемы ”И-НЕ”, AНЕ  аппаратные затраты схемы ”НЕ”, AПС  аппаратные затраты ПС.
Задержка матричного умножителя чисел в дополнительном
коде составляет доп.код = max{И, И–НЕ} + (2n2)ПС + НЕ,
где И – задержка схемы “И”, И–НЕ  задержка схемы “И-НЕ”,
НЕ – задержка схемы “НЕ”, ПС  задержка полного сумматора.
При n = 4, Aдоп.код = 10AИ + 6AИ–НЕ + 12AПС + AНЕ, доп.код =
= max{И, И–НЕ} + 6ПС + НЕ.
Схема матричного умножителя чисел в дополнительном коде
приведена на рисунке (см.рис. 10). Пример матричного умножителя для чисел A = (1011)(2) = 5(10), B = (1101)(2) = 3(10) представлен
на рис. 11. Результат P = (00001111)(2) = 15(10).
2.3 . Алгоритм Бо – Вули
Бо и Вули [3] предложили другую интерпретацию матричного
умножения чисел в дополнительном коде.
16
P = A  B = (a323 + a222 + a121 + a020) (b3 23 + b222 +
+ b121 + b020) = a3b326 + (a2b022 + a1b021 + a0b020 + a2b123 +
+ a1b122 + a0b121 + a2b224 + a1b223 + a0b222)  (a3b225 +
+ a3b124 + a3b023 + a2b325 + a1b324 + a0b323).
(12)
При формировании произведения P необходимо учитывать знаки битов частичных произведений. Можно выделить отдельно биты
частичных произведений, имеющих положительный знак (верхние три строки матрицы на рис. 12) и отрицательный знак (нижние
две строки матрицы на рис. 12).
Произведение формируется сложением первых трех частичных
произведений и вычитанием последних двух строк. Основная идея
заключается в том, чтобы заменить операцию вычитания частичных произведений сложением с их дополнением. Величина дополнения для отрицательного трехразрядного числа X с учетом (8)
определяется следующим образом:
X = -(0 ⋅ 23 + x2 22 + x1 21 + x0 20 ) = -23 + x2 22 + x1 21 + x0 20 + 1. (13)
Выделим в произведении P компоненты, имеющие отрицательный знак:
N =  (a3b225 + a3b124 + a3b023 + a2b325 + a1b324 +
+ a0b323) = 23 · (a3b222 + a3b121 + a3b020)  23 
(b3a222 + b3a121 + b3a020) = U + V,
(14)
где U = 23 · (a3b222 + a3b121 + a3b020), V = 23 · (b3a222 + b3a121 +
+ b3a020).
x
a3
a2
a1
a0
b3
b2
b1
b0
a2 b2
a1b0
a0 b0
a0b1
a2 b1
a1 b1
a2 b2
a1 b2
a0 b2
0
b3 a2 b3 a1
b3 a0
0
0
a3 b2 a3 b1
a3 b0
p7
p6
p5
+
a3 b3
0
0
p4
p3
p2
p1
p0
Рис. 12. Матрица умножения 4-разрядных чисел со знаком
17
Учитывая (13) имеем:
U = -23 ⋅ (a3b2 22 + a3b1 21 + a3b0 20 ) =
= 23 ⋅ (-23 + a3b2 22 + a3b1 21 + a3b0 20 + 1).
(15)
Если множимое положительно, т. е. a3 = 0, то U = 0, в противном
случае (a3 = 1) имеем: U = 23 ⋅ (-23 + b2 22 + b1 21 + b0 20 + 1).
Тогда (15) можно представить:
U = 23 ⋅ (-23 + a3 b2 22 + a3 b1 21 + a3 b0 20 + a3 + a3 23 ).
(16)
Аналогично для V можно записать:
V = 23 ⋅ (-23 + b3 a2 22 + b3 a1 21 + b3 a0 20 + b3 + b3 23 ).
(17)
Тогда, на основе (16) и (17) имеем:
N = -27 + a3 b2 25 + a3 b1 24 + a3 b0 23 + a3 23 + a3 26 +
+b3 a2 25 + b3 a1 24 + b3 a0 23 + b3 23 + b3 26 ).
(18)
Выражения (12) и (18) позволяют сформировать матрицу умножения чисел по алгоритму Бо – Вули (рис. 13). Отметим, что вычитание 1 в столбце с весом 7 заменяется сложением с 1, учитывая
особенности операции сложения по модулю 2. Соответствующий
матричный умножитель приведен на рис. 14.
Отметим преимущества алгоритма Бо – Вули:
1. Биты частичных произведений формируются только логической операцией ”И” между битами множимого и множителя, т. е.
x
a3
a2
a1
a0
b3
b2
b1
b0
a2b0
a1b0
a0b0
a2 b1 a1 b1
a1 b2 a0 b2
a0b1
a3b
0
a3 b1
a3 b2 a2 b2
+
a3 b3 b3 a2 b3 a1
a3
1
b3
p7
p6
b3 a0
a3
b3
p5
p4
p3
p2
p1
p0
Рис. 13. Матрица умножения 4-разрядных чисел
по алгоритму Бо – Вули
18
a3b0
a2b0
0
a2b1
a3b1
a3b3
1
ПС
a3
b3
ПС
a3b2
ПС
a2b3
ПС
a1b3
ПС
ПС
ПС
a1b2
ПС
a0b0
0
a1b1
ПС
a2b2
a1b0
0
a0b1
ПС
a0b2
a0b3
a3
ПС
ПС
ПС
ПС
p7
p6
p5
p4
ПС
p
3
b3
p2
p1
p0
Рис. 14. Матричный умножитель 4-разрядных чисел
по алгоритму Бо – Вули
нет различных операций “И” и “И-НЕ” как это было в предыдущем
алгоритме.
2. Каждый бит частичного произведения имеет положительный
коэффициент, т. е. отсутствуют операции вычитания.
В качестве недостатков алгоритма можно отметить:
1. Надо иметь инверсии каждого бита множимого и множителя
для формирования битов частичного произведения.
2. Надо иметь 5 особенных частичных битов произведения a3,
b3, a3 , b3 , 1.
3. На последних этапах работы требуются дополнительные сумматоры, из-за чего регулярность схемы нарушается.
Аппаратные затраты умножителя, реализующего алгоритм Бо –
Вули определяются как: AБо – Вули = 2n ·AНЕ + n2AИ + [n(n 1)+3]
AПС, где AИ  аппаратные затраты схемы ”И”, AНЕ  аппаратные
затраты схемы ”НЕ”, AПС  аппаратные затраты ПС.
Задержка матричного умножителя чисел в дополнительном
коде по алгоритму Бо – Вули составляет Бо – Вули = НЕ + И +
+ 2n ПС, где И  задержка схемы “И”, НЕ  задержка схемы
“НЕ”, ПС  задержка полного сумматора.
19
При n = 4, AБо – Вули = 8AНЕ + 16AИ + 15AПС, Бо – Вули =
= НЕ + И + 8ПС.
0
0
1
0
0
0
0
1
0
ПС
ПС
1
ПС
0
1
p6
p5
0
0
0
0
ПС
0
1
1
ПС
1
0
ПС
1
ПС
1
1
ПС
1
0
p7
0
0
0
0
1
1
0
1
0
0
ПС
1
0
0
1
ПС
0
1
0
0
ПС
1
ПС
1
0
ПС
0
0
ПС
1
0
ПС
1
1
0
0
1
p4
p3
p2
p1
p0
0
1
1
1
1
Рис. 15. Умножение чисел -5 и -3 по алгоритму Бо – Вули
0
1
0
0
0
1
0
1
0
ПС
0
ПС
ПС
0
1
p6
p5
1
1
1
0
0
1
ПС
0
1
0
1
1
1
p7
0
ПС
0
ПС
0
ПС
0
1
0
ПС
0
1
0
0
0
1
1
ПС
1
ПС
0
ПС
0
ПС
0
0
1
0
ПС
0
0
1
0
1
ПС
0
0
ПС
0
1
0
0
1
p4
p3
p2
p1
p0
1
0
0
0
1
Рис. 16. Умножение чисел 5 и 3 по алгоритму Бо – Вули
20
На рис. 15 приведен пример умножения чисел A = (1011)(2) =
= 5(10) и B = (1101)(2) = 3(10) по алгоритму Бо – Вули. Результат
P = (00001111)(2) = 15(10). На рис. 16 по алгоритму Бо – Вули перемножаются числа A = (0101)(2) = 5(10) и B = (1101)(2) = 3(10). Результат P = (11110001)(2) = 15(10).
2.4 . Алгоритм Пезариса
Рассмотрим другой матричный умножитель, выполняющий
непосредственное умножение чисел в дополнительном коде без дополнительных преобразований, которые имеют место в алгоритме
Бо – Вули. Этот алгоритм был предложен Пезарисом [4]. На рис. 17
представлена матрица умножения четырехразрядных чисел в дополнительном коде. На рисунке жирным начертанием выделены
биты, имеющие отрицательный вес.
Умножитель Пезариса использует различные типы полных
сумматоров (рис. 18), у которых некоторые входы и выходы могут
иметь отрицательный вес. Полный сумматор типа 0 (ПС0)  обычный одноразрядный сумматор, не имеющий отрицательных входов. Сумматор типа 1 (ПС1) имеет один отрицательный вход, а его
модифицированная версия  тип 2 (ПС2) имеет два отрицательных
входа. Аналогично, сумматор типа 3 (ПС3) с тремя отрицательными входами  модифицированная версия ПС0. Индекс в обозначении полного сумматора определяет его тип и вместе с тем число отрицательных входов этого сумматора.
a 3a 2 a 1 a 0
b 3b 2 b 1 b 0
x
+
a 3b 3
p7
p6
a 3b 2
a 2b 3
p5
a 3b 1
a 2b 2
a 1b 3
a 3b 0 a 2b 0 a 1b 0 a 0b 0
a 2b 1 a 1b 1 a 0b 1
a 1b 2 a 0b 2
a 0b 3
p4
p3
p2
p1
p0
Рис. 17. Матрица умножения 4-разрядных чисел
в дополнительном коде
21
a
b
p
ПС 0
c
a
c
c
s
b
a
p
ПС 2
p
ПС 1
s
a
b
b
p
ПС 3
s
c
s
Рис. 18. Различные типы полных сумматоров
Арифметические зависимости между входами и выходами этих
сумматоров выглядят следующим образом:
ПС0: с21 + s20 = a20 + b20 + p20,
ПС1: с21 + (s) 20 = a20 + b20 + (p)20,
ПС2: (с)21 + s20 = (a)20 + (b)20 + p20,
ПС3: (с)21 + (s)20 = (a)20 + (b)20 + (p)20.
Ниже приведены таблицы истинности для различных типов
полных сумматоров (табл. 1–4).
Таблица 1
Таблица истинности ПС0
22
a20
b20
p20
c21
s20
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
1
0
0
1
Таблица 2
Таблица истинности ПС1
a20
b20
(p)20
c21
(s)20
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
0
1
Таблица 3
Таблица истинности ПС2
(a)20
(b)20
p20
(c)21
s20
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
0
1
Таблица 4
Таблица истинности ПС3
(a)20
(b)20
(p)20
(c)21
(s)20
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
1
0
0
1
Матричный умножитель Пезариса для четырехразрядных чисел со знаком представлен на рис. 19. Полные сумматоры на рисунке изображены в виде прямоугольников, внутри которых ука23
зываются слагаемые и их знаки. Жирным начертанием выделена
рамка сумматора, на который стоит обратить отдельное внимание.
Его выход s является выходом p3 произведения и должен иметь положительный вес. Но так как этот сумматор относится к первому
типу, то для него: a + b  p = 2c  s, и, следовательно, выход s имеет
отрицательный вес. Так как: 2c  s = 2c + s  2s. то мы можем допустить, что выход сумматора имеет положительный вес, но при этом
необходимо сигнал s со знаком ““ подать на вход сумматора, который расположен на одну позицию правее (его вход несет двойной
вес). На рис. 19 этот сумматор выделен темно-серым цветом, а вход
этого сумматора жирным начертанием.
Матричный умножитель Пезариса с указанием типов полных
сумматоров приведен на рис. 20. Аппаратные затраты умножителя
Пезариса определяются как: AПезариса = n2AИ + n (n  1) AПС, где
AИ – затраты схемы ”И”, AПС  затраты ПС. Задержка умножителя
Пезариса составляет Пезариса = И + (2n2)ПС, где И  задержка
схемы ”И”, ПС  задержка полного сумматора. При n = 4, AПезариса
= 16AИ + 12AПС, Пезариса = И + 6ПС. Задержка умножителя показана на рис. 19.
(-c)
(-0)
(+0)
(+ 0)
-a3b0+a2b1
a2b0+a1b1
a1b0+a0b1
(+s) (+c)
-a3b1+a2b2
(-c)
(+s) (+c)
-a3b2-a2b3
(-c)
(-s)
(+c)
(-s)
(-c)
p7
+a3b3
(+s)
(+s)
-a0b3
p0
+ a0b2
p1
(+s)
p4
Задержка в 'ПС,
где 'ПС – время задержки схемы
полного сумматора
2
4
5
p5
6
p6
Рис. 19. Матричный умножитель Пезариса
24
1
3
(-s)
p3
0
p2
(+c)
+
(-c)
(+s) (+c)
(+s) (+c)
-a1b3
+
(-c)
+a1b2
a0b0
a3b0
a2b0
a1b0
0
a2b1
a3b1
p7
a2b2
a2b3
a3b3
ПС3
ПС2
ПС2
ПС2
p6
p5
p4
ПС0
a1b2
ПС0
a1b3
ПС1
0
a1b1
ПС2
ПС2
a3b2
a0b0
0
a0b1
ПС0
a0b2
ПС0
a0b3
ПС1
p3
p2
p1
p0
Рис. 20. Матричный умножитель Пезариса с указанием типов
полных сумматоров
x (1) 0 1 1 = -5
(1) 1 0 1 = -3
1
(1) 0 1 1
(0) 0 0 0
(1) 0 1 1
+ 1 (0) (1)(1)
1
1
1
ПС2
0
0
ПС3
0
ПС1
1 0
0 1
ПС2
0
0
1
ПС1
ПС0
1
0
0
0
ПС0
0
1
0
ПС2
1
1
1
0
0
ПС2
0
0 0 0 0 1 1 1 1 = 15
1
0
0
1
ПС0
0
ПС0
0
1
1
1
0
1
1
ПС2
1
0
0
0
p7
p6
p5
p4
p3
p2
p1
p0
0
0
0
0
1
1
1
1
Рис. 21. Умножение чисел 5 и 3 по алгоритму Пезариса
25
На рисунке приведен пример умножения чисел A = (1011)(2) =
= 5(10) и B = (1101)(2) = 3(10) по алгоритму Пезариса (см. рис. 21).
Результат P = (00001111)(2) = 15(10).
2.5 . Модифицированный алгоритм Пезариса
Модифицированный алгоритм Пезариса предполагает использование ограниченного количества типов полных сумматоров. Различают двухсекционные и трехсекционные матричные умножители.
Двухсекционные матричные сумматоры используют сумматоры
ПС0 и ПС2, а трехсекционные  ПС0, ПС1 и ПС2. Двухсекционный
матричный умножитель Пезариса представлен на рис. 22.
Аппаратные затраты модифицированного двухсекционного и
трехсекционного матричного умножителей Пезариса совпадают с
затратами стандартного алгоритма Пезариса.
a2b0
a1b0
0
a1b1
ПС0
a2b1
ПС0
a2b2
ПС0
ПС0
a3b1
a3b2
a3b3
p7
ПС2
a2b3 ПС
2
ПС2
ПС2
ПС2
p6
p5
p4
a1b2
ПС 0
a0b0
0
a0b1
ПС0
a0b2
0
a3b0
a1b3 ПС
2
a0b3
0
p3
p2
p1
p0
,
Рис. 22. Двухсекционный матричный умножитель Пезариса
26
Задержка двухсекционного умножителя Пезариса составляет
Пезариса2 = И + (2n1)ПС, где И – задержка схемы ”И”, ПС – задержка полного сумматора. При n = 4, Пезариса2 = И + 7ПС.
На рис. 23 приведен пример двухсекционного матричного умножителя Пезариса чисел A = (1011)(2) = 5(10) и B = (1101)(2) = 3(10).
Результат P = (00001111)(2) = 15(10).
Трехсекционный матричный умножитель Пезариса представлен на рис. 24. Задержка трехсекционного умножителя Пезариса
составляет Пезариса3 = И + (2n-2)ПС, где И – задержка схемы
”И”, ПС – задержка полного сумматора. При n = 4, Пезариса3 =
= И + 6ПС.
На рис. 25 приведен пример трехсекционного матричного умножителя Пезариса чисел A = (0011)(2) = 3(10) и B = (1011)(2) =
= 5(10). Результат P = (11110001)(2) = 15(10). На рис. 26 приведен
x (1) 0 1 1 = -5
(1) 1 0 1 = -3
ПС0
0
1
ПС2
ПС2
0
0
ПС0
0
1
ПС2
0
1
ПС2
1
1
0
1
1
1
0
1
1
1
1
ПС2
0
0
ПС0
0
1 ПС
0
0
0
ПС0
0
0
1
1
0
0
ПС0
0
0
1
1
0
0 0 0 0 1 1 1 1 = 15
1
1
0
(1) 0 1 1
(0) 0 0 0
+ (1) 0 1 1
1 (0) (1)(1)
0
ПС2
0
0
0
0
p7
p6
p5
p4
p3
p2
p1
p0
0
0
0
0
1
1
1
1
Рис. 23. Двухсекционный матричный умножитель Пезариса
чисел 5 и 3
27
a3b0
a2b0
a1b0
0
p7
ПС1
a2b2
ПС1
a3b2
a2b3
0
a2b1
a3b1
a1b3
a3b3
ПС2
ПС2
ПС2
ПС2
p6
p5
p4
ПС2
a1b2
0
a1b1
ПС0
ПС1
a0b0
a0b1
ПС0
a0b2
ПС0
a0b3
ПС 2
0
p3
p2
p1
p0
Рис. 24. Трехсекционный матричный умножитель Пезариса
(0) 0 1 1 = 3
(1) 0 1 1 = -5
x
(0) 0 1 1
(0) 0 1 1
(0) 0 0 0
0 (0) (1)(1)
0
0
0
0
0
ПС2
0
1
0
ПС2
0
0
1
ПС2
1 0
1
ПС2
ПС1
ПС2
1
0
1
ПС0
0
0
ПС1 0
0
ПС2
1
0
0
ПС1
0
1 1 1 1 0 0 0 1 = -15
0
0
0
0
1
ПС0
1
ПС0
1
0
0
0
1
1
0
0
0
1
1
1
p7
p6
p5
p4
p3
p2
p1
1
1
1
1
0
0
0
1
Рис. 25. Трехсекционный матричный умножитель Пезариса чисел 3 и –5
28
(1) 0 1 1 = -5
(1) 1 0 1 = -3
x
(1) 0 1 1
(0) 0 0 0
(1) 0 1 1
1 (0) (1)(1)
1
0
0
0
0
1
ПС 2
0
ПС2
1 1
1 1
ПС 2
0
0
1
ПС2
ПС1
ПС2
1
0
0
ПС0
0
1
ПС1 0
1
ПС2
1
0
0
ПС1
0
0 0 0 0 1 1 1 1 = 15
1
0
0
1
0
ПС0
0
ПС0
0
1
1
1
0
1
1
0
0
0
0
0
p7
p6
p5
p4
p3
p2
p1
p0
0
0
0
0
1
1
1
1
Рис. 26. Трехсекционный матричный умножитель Пезариса
чисел 5 и 3
пример трехсекционного матричного умножителя Пезариса чисел
A = (1011)(2) = 5(10) и B = (1101)(2) = 3(10). Результат P = (00001111)(2) =
= 15(10).
Вывод: по сравнению с умножителем Бо – Вули умножитель Пезариса имеет более регулярный вид, но при этом используются несколько типов сумматоров.
29
3. ДРЕВОВИДНЫЕ УМНОЖИТЕЛИ
Умножители, построенные по древовидной структуре, позволяют сократить задержку, присущую матричным умножителям.
Если матричные умножители содержат n строк сумматоров, то в
древовидных умножителях число ступеней суммирования меньше,
так как на каждой ступени выполняется большее число операций
сложения, чем в матричном умножителе. При этом главный недостаток древовидных схем – дополнительные провода для связи
разрядов, имеющих одинаковый вес. Как следствие, нерегулярная
структура и большая площадь занимаемая схемой на кристалле
умножителя.
3.1. Изображение схем умножителей
Для изображения схем умножителей используют точечные и
цифровые диаграммы.
3.1.1. Точечные диаграммы
На точечных диаграммах изображаются отдельные биты числа,
с учетом веса, которые должны быть сложены для получения конечного результата. Каждой точке соответствует один бит числа.
Положение точки по горизонтали определяет вес двоичного разряда. На рис. 27 представлена точечная диаграмма для четырехразрядного числа A = (a3a2a1a0)(2) = a323 + a222 + a121+ a020.
Разрядам с одинаковым весом соответствуют точки, расположенные на одной вертикали. В силу коммутативности операции
сложения положение точки по вертикали не имеет значения. На
рис. 28 приведена точечная диаграмма суммы двух четырехразрядных чисел.
Рис. 27. Точечная диаграмма четырехразрядного числа
Рис. 28. Точечная диаграмма суммы
двух 4-разрядных чисел
30
Точечная диаграмма произведения четырехразрядных чисел
(рис. 29) имеет n2 точек. При этом весу 0 соответствует одна точка,
весу 1 – две и т.д.
Максимальное количество точек на одной вертикали называется высотой точечной диаграммы. Точечная диаграмма результата имеет высоту 1. Высота диаграммы сложения двух чисел равна
двум. Высота диаграммы умножения двух n-разрядных чисел – n.
Для вычисления результата необходимо преобразовать диаграмму, чтобы ее высота стала равна 1. Для этого используют операцию
сжатия (компрессии) точечной диаграммы при помощи полного
одноразрядного сумматора и полусумматора. Полный одноразрядный сумматор преобразует диаграмму высоты 3 в диаграмму высоты 1, а полусумматор – диаграмму высоты 2 в диаграмму высоты 1
(рис. 30).
При преобразовании точечных диаграмм новая диаграмма рисуется под исходной и отделяется от нее горизонтальной чертой. Если
точки преобразованной диаграммы являются выходом полного
сумматора, то они соединяются линией, если выходом полусумматора – линией со штрихом. Высота выходной диаграммы на рис. 30
равна 1.
Точечная диаграмма для матричного умножителя Брауна, рассмотренного в разделе 1, приведена на рис. 31. Предполагается, что
сомножители – шестиразрядные.
Рис. 29. Точечная диаграмма произведения
двух 4-разрядных чисел
Рис. 30. Преобразование точечных диаграмм
при помощи полного сумматора и полусумматора
31
Рис. 31. Точечная диаграмма матричного умножителя Брауна
32
На диаграмме показаны используемые полусумматоры и полные сумматоры. Для преобразования точечной диаграммы высоты
2 в результат можно использовать сумматор с параллельным переносом. Для построения схемы умножителя используется 20 полных
сумматоров, 5 полусумматоров и схема параллельного переноса.
Ранее, при построении умножителя Брауна, использовались только полные сумматоры (на третий вход полусумматора подавался 0).
3.1.2. Цифровые диаграммы
Цифровая диаграмма – компактный способ представления точечной диаграммы. На ней указывается высота каждой вертикали.
Цифровая диаграмма произведения четырехразрядных чисел приведена на рис. 32, а матричного умножителя Брауна для шестиразрядных чисел – на рис. 33.
На цифровой диаграмме показаны элементы (ПС и 1/2С), используемые при построении умножителя. На заключительном этапе используется схема сумматора с параллельным переносом на 5
входов.
1
2
3
4
3
2
1
Рис. 32. Цифровая диаграмма произведения
двух 4-разрядных чисел
1
2
3
4
1
2
3
4
1
2
3
1
2
1
1
5
6
5
4
3
2
1
1/2С 1/2С 1/2С 1/2С 1/2С
6
6
5
4
3
1
ПС ПС ПС ПС ПС
5
5
5 4
3 1
ПС ПС ПС ПС ПС
1
1
1
1
1
1
1
1
1
4
4
4
4 3
1
ПС ПС ПС ПС ПС
3
3
3
3
3 1
ПС ПС ПС ПС ПС
1
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Рис. 33. Цифровая диаграмма
матричного умножителя Брауна
33
3.2 . Алгоритм работы древовидного умножителя
Алгоритм работы древовидного умножителя состоит из трех
шагов.
Шаг 1. Формируются биты ЧП при помощи n2 элементов “И”.
Шаг 2. Производится сжатие (компрессия) ЧП с использованием дерева параллельных сумматоров, служащего для сведения ЧП
к вектору сумм и вектору переносов. Сжатие производится в несколько этапов редукции, причем каждый этап вносит задержку,
присущую полному сумматору. Сжатие выполняется при помощи
схем полного одноразрядного сумматора (счетчика (3,2)) и полусумматора (счетчика (2,2)). Название “счетчик”, введенное Дадда
в [6], говорит о том, что код на выходах cs соответствует числу единиц, поданных на входы схемы.
Шаг 3. Выполняется заключительное суммирование вектора
сумм и вектора переносов для получения конечного результата.
Обычно на этом шаге применяются быстрые схемы суммирования,
например, схема с параллельным распространением переноса.
Известные древовидные умножители различаются способом сокращения числа ЧП (шаг 2 алгоритма), а именно способом формирования вектора сумм и вектора переносов.
Рассмотрим три наиболее известные схемы суммирования ЧП:
дерево Уоллеса [5], дерево Дадда [6] и перевернутое ступенчатое дерево [7].
3.3 . Дерево Уоллеса
В операции умножения сложение ЧП занимает наибольшее
время. Дерево Уоллеса – сумматор, который складывает все биты
с одинаковым весом (двоичные разряды одного столбца). Дерево Уоллеса с тремя входами для сложения трех бит с одинаковым
весом W3 (рис. 34) представляет собой полный одноразрядный
сумматор с сохранением переноса. На рис. 35 показано дерево
Уоллеса с семью входами W7, который формируется из четырех
деревьев W3.
Дерево Уоллеса с k-входами – схема суммирования k-разрядов с
одинаковым весом имеет log2(k+1) выходов, где x – ограничение
величины x до наибольшего целого.
Алгоритм Уоллеса предполагает, что строки матрицы ЧП группируются по 3. Полные сумматоры используются для сжатия
34
2i
2i
2i
ПС
c
s
2 i+1
2i
Рис. 34. Дерево Уоллеса для трех входов
2i
2i
ПС
2i
c
c
c
s
2i
2i
2i
ПС
2i
s
ПС
s
c
ПС
s
2i+2
2i+1
2i
Рис. 35. Дерево Уоллеса для семи входов
столбцов с тремя битами, а полусумматоры – с двумя. Строки, не
попавшие в набор из трех строк, учитываются на следующем этапе
редукции.
Высота промежуточной матрицы (количество строк) на i-м этапе
определяется как: h1 = n, hi+1 = 2 hi/3 + hi mod 3, где i  1, x – выделение целой части числа x и mod – операция взятия остатка. Вычисление высоты выполняется пока hi > 2. Например, для 12-разрядного умножителя Уоллеса мы имеем:
h1 = 12, h2 = 8, h3 = 6, h4 = 4, h5 = 3, h6 = 2.
35
a3b1
ПС
a3b2
a3b3
p7
ПС
a2b3
ПС
a2b0
a3b0
a1b3
a2b1
a2b2
0
ПС
a1b2
a0b3
0
ПС
ПС
ПС
p6
p5
p4
p3
a0b0
0
a1b1
ПС
ПС
a1b0
ПС
ПС
p2
a0b2
ПС
a0b1
0
p1
p0
Рис. 36. Суммирование ЧП с помощью дерева Уоллеса
Дерево Уоллеса для четырехразрядного умножителя приведено на рис. 36. Схему можно ускорить, если на последнем этапе использовать схему сумматора с параллельным переносом. Пример
дерева Уоллеса для умножения чисел 13(10) = (1101)(2) и 11(10) =
= (1011)(2) приведен на рис. 37. Результат умножения P = 143(10) =
= (10001111)(2).
Следует отметить, что при разрядности n=4 параметры задержки и аппаратных затрат совпадают с одноименными параметрами
умножителя Брауна. Поэтому схему Уоллеса выгодно использовать для перемножения чисел большой разрядности.
Рассмотрим дерево Уоллеса для суммирования ЧП при перемножении шестиразрядных чисел. Имеем следующие высоты промежуточных матриц: h1 = 6, h2 = 4, h3 = 3, h4 = 2. Точечная диаграмма, иллюстрирующая дерево Уоллеса приведена на рис. 38,
а соответствующая цифровая диаграмма – на рис. 39. На этапе 4
используется схема сложения с параллельным переносом на семь
входов. Аппаратные затраты схемы составляют: 17 полных сумматоров, 10 полусумматоров и схема сумматора с параллельным переносом на 7 входов.
Отметим, что избыточность кодирования, заложенная в алгоритме Уоллеса, позволяет построить и другие варианты дерева, не
отличающиеся по параметрам от рассмотренного здесь варианта.
36
1
0
1
0
1
0
1
ПС
1
0
0
1
1
ПС
0
1
0
1
ПС
ПС
0
0
1
0
0
0
0
1
ПС
ПС
p5
p4
p3
p2
p1
p0
0
0
1
1
1
1
Этап 3
Этап 2
Этап 1
Рис. 37. Пример дерева Уоллеса для умножения чисел 13 и 11
Этап 4
1
p6
0
1
0
1
ПС
0
0
ПС
0
0
p7
0
ПС
1
1
1
1
0
0
ПС
1
ПС
1
0
ПС
1
0
0
Рис. 38. Точечная диаграмма дерева Уоллеса
для умножения 6-разрядных чисел
37
1
1
2
3
4
5
6
5
4
3
2 1
ПС ПС ПС ПС ПС ПС ПС 1/2С
1/2С ПС 1/2С
3
2
4
4
4
3
3
2
1 1
ПС 1/2С ПС ПС ПС ПС ПС 1/2С
2
2
2
3
3
3
2
2 1
1/2С 1/2С 1/2С ПС ПС ПС 1/2С 1/2С
1
2
2
2
2
2
2
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
Рис. 39. Цифровая диаграмма дерева Уоллеса
для умножения 6-разрядных чисел
3.4 . Дерево Дадда
При умножении чисел небольшой разрядности более распространена другая схема сжатия ЧП – дерево Дадда. Если в алгоритме Уоллеса сжатие кодов происходит на самых ранних этапах, то в алгоритме Дадда, это делается как можно позже. Наибольший уровень
сжатия наблюдается на завершающих стадиях. При этом удается
сократить число используемых сумматоров по сравнению с деревом
Уоллеса. В таблице 5 приведена зависимость числа этапов редукции
в дереве Дадда в зависимости от разрядности сомножителей.
Таблица 5
Число этапов редукции в дереве Дадда
Разрядность операндов (n)
Число этапов редукции (m)
2
3
4
5-6
7-9
10-13
14-19
20-28
29-42
43-63
64-94
1
2
3
4
5
6
7
8
9
10
11
Алгоритм построения дерева Дадда состоит из следующих этапов.
1. Используя разрядность сомножителей n, по таблице 5 определяем необходимое число этапов редукции m.
38
2. Пусть hi – высота матрицы на этапе редукции i. Устанавливаем hm= 2. Далее, по формуле
(19)
hi–1 = hi*1,5,
где h1 = n и i = m, …, 2, (индекс i меняется от наибольшего к наименьшему) определяем высоты промежуточных матриц для каждого этапа редукции.
Выпишем последовательность высот промежуточных матриц
согласно формуле (1): 2, 3, 4, 6, 9, 13, 19, 28, 42, 63, 94, …
3. Определяем число полных сумматоров и полусумматоров для
каждого столбца промежуточной матрицы на каждом этапе редукции.
В промежуточной матрице i-го этапа умножителя столбцы нумеруются справа налево от 1 до 2n-1 (Hi,1, …, Нi,2n–1).
На i-м этапе умножителя используется минимальное число ПС и
1/2С, позволяющих сократить число битов в столбце высоты hi. Если
высота столбца, включая переносы, равна Hi,j, то число ПС и 1/2С
для столбца с номером j определяется по следующим формулам:
NПС = ( Hi,j – hi+1)/2, N1/2С = (Hi,j – hi+1) mod 2.
4. Построим точечную диаграмму умножителя.
Пример 1. Построить древовидный умножитель шестиразрядных операндов, реализующий алгоритм Дадда.
1. По таблице 5 определяем m = 4.
2. По формуле (1) определяем высоты промежуточных матриц
для каждого этапа. h4 = 2, h3 = h4 * 1,5 = 3, h2 = h3 * 1,5 = 4,
h1 = h2 * 1,5 = 6.
3. Определим число полных сумматоров и полных сумматоров
на каждом этапе редукции.
Первый этап. Преобразование матрицы высоты h1 = 6 в матрицу высотой h2 =4.
H1,1 = H1,11 = 1
H1,2 = H1,10 = 2
H1,3 = 3
H1,4 = H1,9 = 4
H1,5 = 5, NПС = (5 – 4)/2 = 0, N1/2С = (5 – 4) mod 2 = 1
H1,6 = H1,7 = 7, NПС = (7 – 4)/2 = 1, N1/2С = (7 – 4) mod 2 = 1
H1,8 = 6, NПС = (6 – 4)/2 = 1, N1/2С = (6 – 4) mod 2 = 0
Второй этап. Преобразование матрицы высоты h2 = 4 в матрицу высотой h3 =3.
H2,1 = H2,11 = 1
39
H2,2 = H2,10 = 2
H2,3 = 3
H2,4 = 4, NПС = (4 – 3)/2 = 0, N1/2С = (4 – 3) mod 2 = 1
H2,5 = H2,6 = H2,7 = H2,8 = H2,9 = 5, NПС = (5 – 3)/2 =
= 1, N1/2С = (5 – 3) mod 2 = 0
Третий этап. Преобразование матрицы высоты h3 = 3 в матрицу высотой h4 =2.
H3,1 = H3,11 = 1
H3,2 = 2
H3,3 = 3, NПС = (3 – 2)/2 = 0, N1/2С = (3 – 2) mod 2 = 1
H3,5 = H3,6 = H3,7 = H3,8 = H3,9 = H3,10 = 4, NПС = (4 – 2)/2 =
= 1, N1/2С = (4 – 2) mod 2 = 0
Этап 4
Этап 3
Этап 2
Этап 1
Четвертый этап. Преобразование матрицы высоты h4 = 2 в конечное произведение высоты 1. Для этого используется сумматор
со схемой параллельного переноса на 10 входов.
4. Точечная диаграмма умножителя приведена на рис. 40. Цифровая диаграмма умножителя приведена на рис. 41.
Рис. 40. Точечная диаграмма умножителя Дадда
40
1
1
2
1
2
3
4
5
6
5
4
ПС 1/2С 1/2С 1/2С
ПС ПС
3
2
1
4
4
4
3
3
4
3
ПС ПС ПС ПС ПС 1/2С
2
1
1
3
3
3
3
2 2
2 3
2
ПС ПС ПС ПС ПС ПС ПС 1/2С
1
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
Рис. 41. Цифровая диаграмма умножителя Дадда
Как видно из диаграммы схема требует 15 ПС, 5 1/2C и сумматор с параллельным переносом на 10 входов. Для сравнения дерево Уоллеса для реализации требует 16 ПС, 10 1/2C и сумматор
с параллельным переносом на 7 входов. Следовательно, в целом,
аппаратные затраты в схеме Дадда меньше. С другой стороны, на
последнем этапе сложения сумм и векторов, в схеме Уоллеса требуется сумматор с меньшим числом разрядов.
Пример 2. Построить дерево Дадда для перемножения 4-разрядных чисел.
Используя алгоритм построения древовидного умножителя
Дадда, построим точечную диаграмму перемножения 4-разрядных
чисел (рис. 42).
Рис. 42. Точечная диаграмма умножителя Дадда
для 4-разрядных чисел
41
Реализация дерева Дадда представлена на рис. 43, а пример
дерева Дадда для умножения чисел 13(10) = (1101)(2) и 11(10) =
(1011)(2) приведен на рис. 44. Результат умножения P = 143(10) =
(10001111)(2).
3.5. Перевернутое ступенчатое дерево
Деревья Уоллеса и Дадда имеют общий недостаток – нерегулярную структуру, что усложняет их реализацию в интегральном
исполнении. Для решения этой проблемы в [7] был предложен
класс деревьев сумматоров, в которых ССП организуются подобно
перевернутой лестнице (overturned stairs). В дальнейшем, такие
деревья будем называть OS деревьями. OS дерево для сложения 9
операндов (9-входовое дерево) показано на рис. 45. Высота дерева
определяется как мера критического пути дерева сумматоров. Для
примера на рис. 45, а высота дерева – 4(T), где T – время задержки
в ССП, равное времени задержки полного сумматора.
Пронумеруем ССП на рис. 45, а сверху вниз и слева направо. Потом разместим ССПi над ССПi+1, где i = 1…6. Полученное прямоугольное размещение для реализации в интегральном исполнении
представлено на рис. 45, б. Древовидная организация ССП неизбежно приводит к сложным соединениям. Выходы ССП не всегда
могут быть входами соседнего ССП. Вместо этого, они будут прохоa3b1
ПС
a3b2
ПС
a2b2
0
a3b0
a0b0
a2b1
ПС
0
a2b0
a1b1
a1b2
a2b3
ПС
a1b3
ПС
a0b3
0
ПС
a3b3
p7
a0b2
ПС
ПС
ПС
p6
p5
p4
ПС
p3
ПС
p2
a1b0
0
ПС
p1
Рис. 43. Суммирование ЧП с помощью дерева Дадда
42
a0b1
p0
1
1
1
0
0
ПС
0
1
1
ПС
0
1
1
ПС
p6
0
0
0
0
0
0
1
0
0
0
ПС
0
1
1
1
p2
1
p3
1
1
ПС
0
0
p4
0
0
ПС
0
ПС
0
0
p5
0
1
1
0
1
ПС
0
ПС
1
0
p7
1
1 ПС
1
ПС
1
0
ПС
1
0
p0
1
p1
1
Рис. 44. Пример дерева Дадда для умножения чисел 13 и 11
а)
ССП 2
s c
ССП 4
s c
ССП 3
s c
ССП 5
s c
б)
высота = 4
ССП 1
s c
ССП 1
ССП 2
ССП 3
ССП 6
s c
ССП 4
ССП 5
ССП 6
ССП 7
s
c
Корень
ССП 7
c
s
Рис. 45. OS дерево на 9 входов: а – представление; б – реализация
43
a60
ПС
a61
ПС
a50
a30
a40
a51
a41
a10
ПС
a31
ПС
a20
a21
a11
0 0
ПС
0
ПС
ПС
0
ПС
c3
s3
0
0
0
ПС
c2 s2
ПС
c1 s1
ПС
c0
s0
Рис. 46. OS дерево для сложения шести 2-разрядных чисел
(битовые секции)
дить через определенное число ССП, пока не достигнут требуемого
ССП. Число таких вертикальных соединений (vertical feedthroughs
(FT’s)) используют как меру сложности соединения. OS дерево требует трех вертикальных соединений. На уровне слова, FT – соответствующее число проводов (зависит от разрядности слова) и основные устройства – ССП. На битовом уровне, FT – один провод и
основные устройства – полные сумматоры.
Основной подход к разработке древовидного сумматора состоит
из следующих шагов:
1. Создание дерева битовой секции в вертикальном направлении.
2. Повторение этой конструкции соответствующее число раз.
3. Соединение битовых секций в горизонтальном направлении.
При этом получается очень компактное и регулярное размещение. Отметим, что необходимое пространство между битовыми секциями определяется числом FT. Постоянное число FT обеспечивает равномерное распределение проводов и эффективное использо44
вание кремния. Альтернативный подход к разработке начинается
созданием горизонтальных ССП с дальнейшим их соединением в
вертикальном направлении.
Основной подход к построению OS дерева иллюстрирует рис. 46,
где представлено дерево для сложения 6-ти двухразрядных чисел.
Сначала разрабатывается битовая секция дерева (крайняя правая
секция на рисунке). ОS дерево требует четырех таких секций, причем два левые секции являются упрощенными, т. е. из них исключены лишние ПС. Далее битовые слои соединяются в горизонтальном направлении (линии с жирным начертанием).
3.5.1. Описание OS деревьев на уровне слов
Уоллес в [5] ввел описание дерева сумматоров на уровне слов.
Основными строительными блоками OS деревьев являются: корень (рис. 47), соединитель (рис. 47, в), тело и ветвь (рис. 48, 49).
Как показано рис. 49 тело высоты j может быть построено при помощи тела высоты j–1, соединителя и ветви высоты j–2. Соединитель строится из двух ССП, которые имеют 5 входов и 3 выхода
(рис. 47, в; 48, 49). Три выхода соединителя являются входами для
корня дерева. Корень строится из одного ССП. Ветвь и соединитель
в)
ССП
s
c
ССП
s
c
б)
ССП
s
c
Тело
ССП
s
c
Соединитель
а)
ССП
s
c
ССП
s
c
Корень
ССП
s
c
Корень
Рис. 47. OS дерево на уровне слов:
а – с 2-3 входами; б – с 4 входами; в – с 5-6 входами
45
ССП
s
c
ССП
s
c
ССП
s
c
Ветвь
Тело
ССП
s
c
ССП
s
c
ССП
s
c
Соединитель
ССП
s
c
Корень
Рис. 48. OS дерево на уровне слов с 7–9 входами
составляют ступень лестницы. Ветвь высоты j–2 формируется из
j–2 ССП, расположенных друг над другом, с присущими соединениями. Используя эти свойства можно итеративным способом построить OS дерево произвольной высоты.
Число ССП, требуемых для построения OS дерева высоты hOS,
определяется по следующей формуле:
NССП(hOS) = NССП(hOS –1) + hOS – 1, где NССП(1) = 1. (20)
Запишем подобное выражение для числа операндов (входов)
NOS, которые будут складываться в OS дереве:
NOS (hOS) = NOS (hOS –1) + hOS – 1, где NOS (1) = 3.
(21)
Выражение (22) позволяет напрямую определить NOS через hOS
NOS (hOS) = hOS 2/2 – hOS /2 + 3.
(22)
46
Высоты j–2
Ветвь
Тело
высоты j–1
ССП
s
c
Соединитель
Тело
высоты j
ССП
s
c
ССП
s
c
Корень
Рис. 49. OS дерево на уровне слов с произвольным числом входов
На рис. 47–49 представлены OS деревья с разным числом входов.
Высоту дерева hOS как функцию от числа входов NOS можно
определить по следующей формуле:
hOS =1 + (int)(( 8 NOS - 23) / 2) + 0.4),
(23)
где int – приведение к целой части числа путем отсечения дробных
разрядов.
Таким образом, OS дерево может складывать NOS входов за время O( NOS ). В целом, OS деревья медленнее, чем O( log3/2 NW )
деревья Уоллеса, где NW – число входов дерева Уоллеса. Однако,
OS деревья и деревья Уоллеса эквивалентны при N = NOS = NW =
= 3…18, 20…24, 29…31, так как высота вышеуказанных деревьев
при этих значениях N одинакова.
Построенное таким образом OS дерево, называют OS деревом
первого порядка и обозначают OS1. OS деревья более высокого по47
рядка [7] строятся замещением ветви на OS дерево. При этом полученные деревья имеют большую ширину и меньшую высоту при
большем числе входных операндов по сравнению с OS1 деревом.
В данном пособии, подобные деревья рассматриваться не будут.
3.5.2. OS1 дерево для умножения
шестиразрядных операндов
Во-первых, выбираем длину слова – 6 бит. Далее, определяем высоту дерева hOS =1 + (int)(( 8 ⋅ 6 - 23) / 2 + 0.4) =1 + (int)(5 / 2 + 0.4) = 3.
OS1 дерево высоты 3 представлено на рис. 50, а, а его соответствующее горизонтальное размещение на рис. 50, б. Частичные произведения операции умножения, упорядоченные в соответствии с их
весом, представлены на рис. 51. Три верхние строки ЧП объединяются в ССП1, а три нижние образуют ССП2. Полностью содержимое
всех ССП дерева, с использованием точечных диаграмм, показано
на рис. 52. ССП3 суммирует сумму и перенос с выхода ССП1 и сумму с выхода ССП2. ССП4 складывает выходы ССП3 и перенос с выхода ССП2. На рис. 53 представлено OS1 дерево в битовом исполнеб)
ССП1
s
c
а)
ССП1
s
c
ССП2
s
c
ССП2
s
c
ССП3
s
c
ССП3
s
c
ССП4
s
c
ССП4
s
c
Рис. 50. OS1 дерево высоты 3: а – представление; б – реализация
48
a0b 5 a0b 4 a0b 3 a0b 2 a0b 1 a0b 0
a1b 5 a b a1b 3 a1b 2 a b a b
1 4
1 1
1 0
a2b 5 a2b 4
ССП 1
a2b 3 a2b 2 a2b 1 a2b 0
a3b 5 a3b 4 a3b 3 a3b 2 a3b 1 a3b 0
a4b 5 a4b 4 a4b 3 a4b 2 a4b 1 a4b 0
ССП 2
a5b 5 a5b 4 a5b 3 a5b 2 a5b 1 a5b 0
1
2
3
5
4
6
5
4
3
2
1
Рис. 51. Частичные произведения умножения двух 6-разрядных чисел
.
. .
. . .
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . .
. . .
. .
.
ССП1
ССП2
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . . . .
. . . . . .
. . . . . . . .
. . . . . .
.
.
. . . .
. . . .
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . .
. .
.
. . . .
.
. . . . . . . . .
. . . . . . . .
. . . . . .
ССП3
ССП4
. . . . . . . . . . .
. . . . . . . .
Рис. 52. Содержимое ССП дерева
49
50
ПС4
a5b5
0
ПС4
ПС2
a4b5
0
a5b4
0
ПС4
ПС2
a3b5
a5b3
a4b4
a2b5
a5b2
a4b3
ПС1
a2b2
a0b4
a1b3
ПС4
ПС3
ПС4
ПС3
ПС4
ПС3
0
a4b2 a3b2 a4b1 a3b1
0
a5b1
a5b0
a4b0
ПС2
ПС2
ПС2
a3b3
a0b5
a1b5
ПС1
a1b4
a2b3
0
ПС4
ПС3
ПС1
a1b2
Рис. 53. OS1 дерево в битовом исполнении
ПС4
ПС3
ПС2
a3b4
ПС1
a2b4
ПС1
a2b0
0
a3b0 ПС
3
a2b1
a0b3
0
a0b2
a1b1
ПС1
a1b0
0
a0b1
a0b0
51
1
1
1
0
0
1
1
1
ПС4
1
1
1
1
1
1
1
ПС4
ПС3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
ПС4
ПС3
1
1 ПС1
0
0
1
1
ПС4
ПС3
1
1
1
1
0
0
0
1
1
ПС4
ПС3
1
1
0
1
0
ПС4
0
0
0
0
0
Рис. 54. OS1 дерево в битовом исполнении для перемножения чисел 63 и 63
1
0
1
0
1
0
ПС4
ПС2
1
0 0
0
ПС4
1
1
ПС2
1
1 ПС2
1 1
0
1
0
1
1
1
1
1
1
ПС1
ПС1
1 ПС1 1 1 ПС1 1 1 ПС1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
0
1
ПС3
ПС2
ПС2
ПС2
ПС3 1
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
нии. На рисунке использованы обозначения ПС1, ПС2, ПС3 и ПС4,
где индекс указывает номер ССП, к которому относится полный
сумматор.
Пример перемножения двух максимальных шестиразрядных
чисел 63 и 63 представлен на рисунке (см. рис. 54). Соответствующее содержимое дерева ССП на уровне слов для этого примера демонстрирует рис. 55. Здесь входы и выходы каждого ССП указаны
как в двоичной, так и в десятичной системах счисления. Для получения окончательного результата выходы ССП4 надо просуммировать в ускоренном сумматоре с параллельным переносом. Прямоугольный массив, для реализации в интегральном исполнении,
можно получить поворотом массива, представленного в виде ромба,
на рис. 53. При этом получается окончательное дерево для реализации, состоящее из 6 битовых секций. Две крайние правые секции
и две крайние левые секции являются нестандартными. Две центральные секции имеют регулярную структуру. При увеличении
разрядности входных сомножителей, число таких секций будет
увеличиваться и OS1 дерево будет компактным для реализации.
63 126 252
ССП 1
s
c
189
252
111111
111111 ССП
1
111111
s 10111101 189
c 11111100 252
504 1008 2016
s 10111101000 1512
c 11111100000 2016
2016
ССП 2
ССП 2
s
c
1512
10111101
11111100
10111101000 ССП 3
ССП 3
s
c
1449
504
10110101001
00111111000 ССП 4
11111100000
ССП 4
s
c
945
s 10110101001 1449
c 00111111000 504
3024
s 01110110001 945
c 101111010000
Рис. 55. Содержимое дерева ССП на уровне при умножении чисел 63 и 63
52
53
ПС 2
ПС4
a5b5
a4b5
ПС2
a3b5
ПС 2
a3b4
ПС 1
a2b4
0
0
a5b4
a4b4
a5b3
a4b3
a5b2
a1b5
0
0
a2b5
a4b2
a5b1
a0b5
a1b4
a0b4
a1b3
ПС 4
ПС 3
a3b2 a4b1
ab
ПС 2 5 0
ПС 1
a2b2
ПС4
ПС3
ПС2
a3b1
ПС 1
a1b2
0
a4b0
a2b1
a0b3
ПС4
ПС3
ПС 3
ПС 1
a2b0
a3b0
a0b2
a1b1
Рис. 56. OS1 дерево (прямоугольное размещение)
ПС4
ПС 4
ПС3
ПС 2
a3b3
ПС 1
a2b3
ПС4
ПС 4
ПС3
ПС 1
a1b0
0
0
0
a0b1
0
a0b0
3.6. Древовидные умножители в дополнительном коде
Схемы умножения чисел в дополнительном коде, рассмотренные в разделе 2, применительно к матричным алгоритмам умножения могут быть адаптированы к древовидным умножителям.
Пример. Построить деревья Уоллеса и Дадда для четырехразрядных чисел, представленных в дополнительном коде, используя
матрицу умножения чисел в дополнительном коде (рис. 9).
a3b1
ПС
a3b2
a3b3
ПС
ПС
ПС
a2b3
ПС
a2b0
a3b0
a1b3
a2b2
1
a2b1
ПС
ПС
ПС
ПС
p4
p3
a1b2
a1b0
a0b0
0
a1b1
ПС
a0b3 ПС
a0b2
a0b1
ПС
0
0
1
p7
p6
p5
p2
p1
p0
Этап 3
Этап 2
Этап 1
Рис. 57. Суммирование ЧП с помощью дерева Уоллеса
в дополнительном коде
Рис. 58. Точечная диаграмма дерева Уоллеса в дополнительном коде
54
Реализация дерева Уоллеса показана на рис. 57, точечная диаграмма – на рис. 58, а пример умножения чисел –5 и –3 на рис. 59.
Реализация дерева Дадда приведена на рис. 60, точечная диаграмма – на рис. 61, а пример умножения чисел –5 и –3 на рис. 62.
0
ПС
0
1 ПС
1
1
1
ПС
1
0
1
ПС
ПС
0
1
0
ПС
0
1
0
ПС
0
1
0
ПС
0
0
ПС
0
1
1
ПС
0
1
1
1
1
ПС
0
0
0
0
0
ПС
0
0
1
1
0
0
1
0
0
0
1
1
p7
0
p6
0
p5
0
p4
0
p3
1
p2
1
p1
1
p0
1
Рис. 59. Пример дерева Уоллеса для умножения чисел –5 и –3
a3b1
a2b2
a3b0
1
ПС
a3b2
ПС
a0b0
a2b1
0
ПС
a2b0
a1b1
a1b2
a2b3
ПС
a1b3
ПС
a0b3
0
ПС
a3b3
a0b2
ПС
ПС
ПС
ПС
p6
p5
p4
p3
a1b0
0
ПС
ПС
p2
p1
a0b1
1
p7
p0
Рис. 60. Суммирование ЧП с помощью дерева Дадда
в дополнительном коде
55
Рис. 61. Точечная диаграмма дерева Дадда
в дополнительном коде
1
0
1
0
1
ПС
0
0
0
ПС
1
1
0
ПС
1 ПС
0
0
0
0
0
0
ПС
0
1
p6
p5
p4
0
0
0
0
0
0
0
0
0
1
p3
1
1
1
ПС
0
0
p7
0
ПС
ПС
0
0
0
1
ПС
0
0
0
ПС
ПС
1
1
0
ПС
0
1
1
1
p2
p1
p0
1
1
1
Рис. 62. Пример дерева Дадда для умножения чисел –5 и –3
56
ЗАКЛЮЧЕНИЕ
В пособии были рассмотрены основные схемы, используемые
для организации параллельного умножения чисел в ЦВМ. Некоторые схемы, такие как умножитель Брауна, используются только
для умножения целых чисел без знака. Другие схемы позволяют
также перемножать целые знаковые числа, представленные в дополнительном коде.
Древовидные схемы умножения позволяют уменьшить задержку,
присущую матричным умножителям за счет сокращения числа ступеней суммирования, но имеют нерегулярную структуру, что усложняет их реализацию в интегральном исполнении. Перевернутое ступенчатое дерево позволяет решить эту проблему и добиться компактного и регулярного размещения схему умножителя на кристалле.
Следует отметить, что при последовательном умножении большого числа пар сомножителей можно добиться повышения производительности, используя конвейеризацию параллельных умножителей [2]. Схема конвейера может быть применена как к матричным,
так и древовидным умножителям. При этом в матричных умножителях в качестве ступеней конвейера используются строки матрицы
сумматоров, а в древовидных умножителях – каскады сжатия.
57
Библиографический список
1. Марковский С. Г., Марковская Н. В., Суетина Т. А. Алгоритмы умножения в ЦВМ: учеб. пособие. СПб.: ГУАП, 2010. 40 с.: ил.
2. Организация ЭВМ и систем: учебник / Б. Я. Цилькер, С. А. Орлов. 2-е изд. СПб.: Питер, 2011. 686 с.
3. Baugh C. R., Wooley B. A. A Two’s Complement Parallel Array
Multiplication Algorithm. IEEE Transactions on Computers, C-22,
Dec. 1973, pp. 1045–1047.
4. Pezaris S. D. A 40-ns 17b by 17b Array Multiplier. IEEE
Transactions on Computers, C-20, Apr. 1971, pp. 442–447.
5. Wallace C. S. A Suggestion for a Fast Multiplier. IEEE
Transactions on Electronic Computers, EC-13, Feb. 1964, pp. 14–17.
6. Dadda L. Some schemes for parallel multipliers. Alta Frequenza,
Vol. 19, pp. 349–356, May 1965.
7. Mou Z., Jutand F. “Overturned-Stairs” Adder Trees and Multiplier Design. IEEE Transactions on Computers, Vol. 41, No. 8, pp.
940–948, Aug. 1992.
58
ПРИЛОЖЕНИЕ 1
ПРОГРАММА ПРОВЕРКИ ЗНАНИЙ
ПО МАТРИЧНЫМ АЛГОРИТМАМ УМНОЖЕНИЯ
При запуске программы пользователь попадает в окно выбора
алгоритма тестирования (рис. П.1). В данном окне можно выбрать
один из 4-матричных алгоритмов умножения и задать длину разрядной сетки – 4 или 5 бит. По умолчанию, задан алгоритм умножения Брауна для 4-битных сомножителей. После нажатия на
клавишу “OK” пользователь переходит в рабочее окно программы
(окно тестирования – рис. П.2).
Программа случайным образом генерирует значения сомножителей, которые отражаются в окне тестирования. В этом окне необходимо заполнить матрицу сумматоров, т. е. для каждого полного
сумматора указать выходы суммы и переноса. Для ввода значений
используется левая кнопка мыши. При первом нажатии в поле ввода выставляется 0. Каждое последующее нажатие меняет 0 на 1, а
1 на 0.
Рис. П.1. Окно выбора алгоритма
59
60
Рис. П.2. Окно тестирования
61
Рис. П.3. Результаты тестирования
После заполнения всех полей необходимо нажать кнопку “Проверить”. Если не все поля ввода были заполнены, то будет выдано соответствующее предупреждение, и незаполненные поля окрасятся
в желтый цвет. Если пользователь заполнил все поля, то выводятся
результаты тестирования (см. рис. П.3). Выводится ответ пользователя, правильный ответ, количество ошибок, допущенных пользователем при тестировании и оценка. Если были допущены ошибки,
то поля с неверными значениями подсвечиваются оранжевым цветом. Преподаватель определяет количество ошибок, которое может
допустить студент при тестировании. В примере на рис. П.3. студент допустил одну ошибку и получил зачет.
62
ПРИЛОЖЕНИЕ 2
ПРОГРАММА ПРОВЕРКИ ЗНАНИЙ
ПО ДРЕВОВИДНЫМ АЛГОРИТМАМ УМНОЖЕНИЯ
После запуска программы пользователь попадает в окно выбора
алгоритма тестирования (рис. П.4). В данном окне можно выбрать
один из двух древовидных алгоритмов умножения: алгоритм Уоллеса или алгоритм Дадда и задать длину разрядной сетки – 4 или 5 бит.
Кнопка “Изменить настройки” доступна только преподавателю.
После нажатия на клавишу “Начать тестирование” пользователь переходит в окно тестирования (рис. П.5). Программа случайным образом генерирует значения сомножителей, которые отражаются в окне тестирования. В этом окне необходимо заполнить
результаты побитных произведений сомножителей, дерево сумматоров, т. е. для каждого полного сумматора указать выходы суммы
и переноса и выходные биты произведения. Для ввода значений 0
или 1 используется левая кнопка мыши также как в программе тестирования по матричным алгоритмам умножения. На прохождение теста студенту отводится 5 минут. Для этого в программе предусмотрен таймер, который включается при переходе в окно тестирования. После заполнения всех полей необходимо нажать кнопку
“Проверить результат”.
Если не все поля ввода были заполнены, то будет выдано соответствующее предупреждение, и незаполненные поля окрасятся в
желтый цвет. Если пользователь заполнил все поля, то выводится
Рис. П.4. Окно выбора алгоритма
63
64
Рис. П.5. Окно тестирования
65
Рис. П.6. Результаты тестирования
сообщение о прохождении теста (зачет/незачет). Если были допущены ошибки, то указывается их количество и поля с неверными
значениями подсвечиваются красным цветом (см. рис. П.6). В данном примере студент допустил 2 ошибки при тестировании. Если
преподаватель считает, что студент не прошел тест, он может предложить студенту повторно пройти тест. При этом значения сомножителей будут другими.
66
СОДЕРЖАНИЕ
Предисловие ....................................................................
1. Матричное умножение чисел без знака .............................
1.1. Матрица сумматоров ...............................................
1.2. Сумматор с сохранением переноса .............................
1.3. Характеристики матричных умножителей .................
2. Матричное умножение чисел со знаком.............................
2.1. Основы умножения чисел в дополнительном коде .......
2.2. Матричный алгоритм умножения в дополнительном
коде ............................................................................
2.3. Алгоритм Бо – Вули ................................................
2.4. Алгоритм Пезариса .................................................
2.5. Модифицированный алгоритм Пезариса ....................
3. Древовидные умножители ..............................................
3.1. Изображение схем умножителей ...............................
3.1.1. Точечные диаграммы ........................................
3.1.2. Цифровые диаграммы.......................................
3.2. Алгоритм работы древовидного умножителя ..............
3.3. Дерево Уоллеса .......................................................
3.4. Дерево Дадда ..........................................................
3.5. Перевернутое ступенчатое дерево ..............................
3.5.1. Описание OS деревьев на уровне слов ..................
3.5.2. OS1 дерево для умножения шестиразрядных
операндов ................................................................
3.6. Древовидные умножители в дополнительном коде .......
Заключение .....................................................................
Библиографический список ................................................
Приложение 1. Программа проверки знаний по матричным
алгоритмам умножения .....................................................
Приложение 2. Программа проверки знаний по древовидным
алгоритмам умножения .....................................................
3
5
5
7
11
13
13
14
16
21
26
30
30
30
33
34
34
38
42
45
48
54
57
58
59
63
67
Учебное издание
Марковский Станислав Георгиевич
Марковская Наталья Владимировна
Суетина Татьяна Александровна
ПАРАЛЛЕЛЬНОЕ УМНОЖЕНИЕ
В ЦВМ
Учебное пособие
В авторской редакции
Верстальщик С. Б. Мацапура
Сдано в набор 02.10.12. Подписано к печати 12.10.12.
Формат 6084 1/16. Бумага офсетная. Усл. печ. л. 3,95.
Уч.-изд. л. 4,42. Тираж 100 экз. Заказ № 534.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
0
Размер файла
419 Кб
Теги
markovskiimarksyetina
1/--страниц
Пожаловаться на содержимое документа