Матричный метод умножения

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

Таблица 4.4

и типа применяемых сумматоров. Рассмотрим схему умножения на примере двух шестиразрядных чисел:

Эту схему умножения можно представить в виде матрицы (табл. 4.4), каждый элемент которой равен 0 или 1 для

Для получения произведения двух чисел элементы матрицы надо суммировать в следующем порядке:

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

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

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

если только все конъюнкции вида поступают на

Рис. 4.5

Рис. 4.6. (см. скан)

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

Существенный вклад в величину вносит время спуска по вертикали. Отдельная вертикаль в исследуемом дереве представляет собой последовательное соединение одноразрядных сумматоров. Дерево спуска по вертикали можно сделать таким, как показано на рис. 4.7. Если такое дерево имеет ярусов, то справедливо неравенство

где — число слагаемых. Время спуска по этому дереву составит

Указанная организация спуска по вертикали приводит к тому, что дерево сумматоров трансформируется (рис. 4.8). Новое дерево более низкое, чем исходное, и, естественно, что время спуска уменьшается до величины

Рис. 4.7

Рис. 4.8

Рис. 4.9

если только для справедливо

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

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

Когда то ибо в данном случае оказывается, что спуск по вертикали происходит за то же время, что и по диагонали. Если же то ускорение спуска происходит почти в 1,5 раза.

Как следует из соотношения (4.14), время формирования произведения деревом с измененной организацией оказывается приблизительно равным сложению чисел разрядности в сумматоре с последовательным распространением переноса [38].

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

Задачей дерева спуска является сведение частичных произведений к их сумме. Рассмотренная структура дерева спуска не единственная. Будем строить дерево спуска из однотипных параллельных сумматоров, каждый из которых состоит из обычных двоичных одноразрядных сумматоров, не связанных друг с другом. Все частичных лроизведений будем одновременно суммировать на сумматорах. Полученные слагаемых вновь одновременно суммируем на сумматорах и объединяем выходы этих сумматоров в новый массив и т. д. Через А, ступеней мы от слагаемых приходим к двум слагаемым — векторам (рис. 4.9). Наибольшее число слагаемых, которое может быть приведено таким деревом при К ступенях, определится из рекуррентного соотношения

где Если число слагаемых больше, чем значение определенное из (4.15), то число ступеней в дереве спуска должно быть увеличено.

Время спуска по дереву приведенной структуры

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

Рис. 4.10

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

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

Том Например, при

Рис. 4.11

получим . Заметим, что требуемое оборудование существенно отличается для этих двух схем — при итерационном спуске число сумматоров есть и, а при прямом нашем случае эти величины равны 6 и 28 соответственно.

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

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