Множитель Дадда

Множитель Дадда — это аппаратный двоичный умножитель, изобретенный учёным-компьютерщиком Луиджи Дадда в 1965 году. ^[1] Он использует набор полных и половинных сумматоров для поэтапного суммирования частичных произведений ( дерево Дадда или сокращение Дадда ), пока не останется два числа. Конструкция аналогична множителю Уоллеса , но другое дерево редукции уменьшает необходимое количество вентилей (для всех размеров операндов, кроме самых маленьких) и делает его немного быстрее (для всех размеров операндов). ^[2]

Множители Дадды и Уоллеса имеют одинаковые три шага для двухбитовых строк. $w_{1}$ и $w_{2}$ длины $\ell _{1}$ и $\ell _{2}$ соответственно:

Умножьте ( логическое И ) каждый бит $w_{1}$ , по каждому биту $w_{2}$ , уступая $\ell _{1}\cdot \ell _{2}$ результаты, сгруппированные по весу в столбцах
Сокращайте количество частичных произведений поэтапно полными и половинными сумматорами, пока у нас не останется не более двух битов каждого веса.
Сложите конечный результат обычным сумматором.

Как и в случае с множителем Уоллеса, продукты умножения на первом этапе имеют разные веса, отражающие величину исходных битовых значений при умножении. Например, произведение битов $a_{n}b_{m}$ имеет вес $n+m$ .

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

Описание

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

Прогресс редукции контролируется последовательностью максимальной высоты. $d_{j}$ , определяемый:

d_{1}=2

, и

d_{j+1}=\operatorname {floor} (1.5d_{j}).

В результате получается такая последовательность:

d_{1}=2,d_{2}=3,d_{3}=4,d_{4}=6,d_{5}=9,d_{6}=13,\ldots

Начальное значение $j$ выбирается как наибольшее значение такое, что $d_{j}<\min {(n_{1},n_{2})}$ , где $n_{1}$ и $n_{2}$ — количество битов во входных множимом и множителе. Меньшая из двух битовых длин будет максимальной высотой каждого столбца весов после первого этапа умножения. Для каждого этапа $j$ Целью сокращения является уменьшение высоты каждого столбца так, чтобы она была меньше или равна значению $d_{j}$ .

Для каждого этапа от $,\ldots ,1$ , уменьшите каждый столбец, начиная со столбца с наименьшим весом, $c_{0}$ по этим правилам:

Если $\operatorname {height} (c_{i})\leqslant d_{j}$ столбец не требует сокращения, перейти в столбец $c_{i+1}$
Если $\operatorname {height} (c_{i})=d_{j}+1$ добавьте два верхних элемента в полусумматор, поместив результат внизу столбца, а перенос — внизу столбца $c_{i+1}$ , затем перейдите к столбцу $c_{i+1}$
В противном случае добавьте три верхних элемента в полный сумматор, поместив результат внизу столбца, а перенос — внизу столбца. $c_{i+1}$ , перезапуск $c_{i}$ на шаге 1

Пример алгоритма

Пример на соседнем изображении иллюстрирует уменьшение множителя 8 × 8, описанное здесь.

Исходное состояние $j=4$ выбран как $d_{4}=6$ , наибольшее значение меньше 8.

Этап $j=4$ , $d_{4}=6$

$\operatorname {height} (c_{0}\cdots c_{5})$ все они меньше или равны шести битам по высоте, поэтому никаких изменений не происходит.
$\operatorname {height} (c_{6})=d_{4}+1=7$ , поэтому применяется полусумматор, уменьшающий его до шести бит и добавляющий бит переноса к $c_{7}$
$\operatorname {height} (c_{7})=9$ включая бит переноса из $c_{6}$ , поэтому мы применяем полный сумматор и полусумматор, чтобы уменьшить его до шести бит
$\operatorname {height} (c_{8})=9$ включая два бита переноса из $c_{7}$ , поэтому мы снова применяем полный сумматор и полусумматор, чтобы уменьшить его до шести бит
$\operatorname {height} (c_{9})=8$ включая два бита переноса из $c_{8}$ , поэтому мы применяем один полный сумматор и уменьшаем его до шести бит
$\operatorname {height} (c_{10}\cdots c_{14})$ все они меньше или равны шести битам по высоте, включая биты переноса, поэтому никаких изменений не происходит.

Этап $j=3$ , $d_{3}=4$

$\operatorname {height} (c_{0}\cdots c_{3})$ все они меньше или равны четырем битам по высоте, поэтому никаких изменений не происходит.
$\operatorname {height} (c_{4})=d_{3}+1=5$ , поэтому применяется полусумматор, уменьшающий его до четырех бит и добавляющий бит переноса к $c_{5}$
$\operatorname {height} (c_{5})=7$ включая бит переноса из $c_{4}$ , поэтому мы применяем полный сумматор и полусумматор, чтобы уменьшить его до четырех бит
$\operatorname {height} (c_{6}\cdots c_{10})=8$ включая предыдущие биты переноса, поэтому мы применяем два полных сумматора, чтобы уменьшить их до четырех битов.
$\operatorname {height} (c_{11})=6$ включая предыдущие биты переноса, поэтому мы применяем полный сумматор, чтобы уменьшить его до четырех битов.
$\operatorname {height} (c_{12}\cdots c_{14})$ все они меньше или равны четырем битам по высоте, включая биты переноса, поэтому никаких изменений не происходит.

Этап $j=2$ , $d_{2}=3$

$\operatorname {height} (c_{0}\cdots c_{2})$ все они меньше или равны трем битам по высоте, поэтому никаких изменений не происходит.
$\operatorname {height} (c_{3})=d_{2}+1=4$ , поэтому применяется полусумматор, уменьшающий его до трех бит и добавляющий бит переноса к $c_{4}$
$\operatorname {height} (c_{4}\cdots c_{12})=5$ включая предыдущие биты переноса, поэтому мы применяем один полный сумматор, чтобы уменьшить их до трех битов
$\operatorname {height} (c_{13}\cdots c_{14})$ все они меньше или равны трем битам по высоте, включая биты переноса, поэтому никаких изменений не происходит.

Этап $j=1$ , $d_{1}=2$

$\operatorname {height} (c_{0}\cdots c_{1})$ все они меньше или равны двум битам по высоте, поэтому никаких изменений не происходит.
$\operatorname {height} (c_{2})=d_{1}+1=3$ , поэтому применяется полусумматор, уменьшающий его до двух бит и добавляющий бит переноса к $c_{3}$
$\operatorname {height} (c_{3}\cdots c_{13})=4$ включая предыдущие биты переноса, поэтому мы применяем один полный сумматор, чтобы уменьшить их до двух битов.
$\operatorname {height} (c_{14})=2$ включая бит переноса из $c_{13}$ , поэтому никаких изменений не происходит

Добавление

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

См. также

Алгоритм умножения Бута
Слитое умножение-сложение
Дерево Уоллеса
Алгоритм БКМ для комплексных логарифмов и экспонент
Умножение Кочанского для модульного умножения

Ссылки

^ Дадда, Луиджи (май 1965 г.). «Некоторые схемы параллельных умножителей». Высокая частота . 34 (5): 349–356.
Дадда, Л. (1976). «Некоторые схемы параллельных умножителей». В Шварцландере, Эрл Э. (ред.). Развитие компьютерного дизайна: основные статьи . Книжная компания Хайден. стр. 167–180. ISBN 978-0-8104-5988-5 . OCLC 643640444 .
^ Таунсенд, Уитни Дж.; Шварцландер-младший, Эрл Э.; Авраам, Джейкоб А. (декабрь 2003 г.). «Сравнение задержек множителей Дадды и Уоллеса» (PDF) . Усовершенствованные алгоритмы обработки сигналов SPIE, архитектуры и реализации XIII . Международное общество . дои : 10.1117/12.507012 .

Дальнейшее чтение

Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы» . четырехблок . Архивировано из оригинала 3 июля 2018 г. Проверено 16 июля 2018 г.

[Dadda_1965-1] Дадда, Луиджи (май 1965 г.). «Некоторые схемы параллельных умножителей». Высокая частота . 34 (5): 349–356.
Дадда, Л. (1976). «Некоторые схемы параллельных умножителей». В Шварцландере, Эрл Э. (ред.). Развитие компьютерного дизайна: основные статьи . Книжная компания Хайден. стр. 167–180. ISBN 978-0-8104-5988-5 . OCLC 643640444 .

[Townsend_2003-2] Таунсенд, Уитни Дж.; Шварцландер-младший, Эрл Э.; Авраам, Джейкоб А. (декабрь 2003 г.). «Сравнение задержек множителей Дадды и Уоллеса» (PDF) . Усовершенствованные алгоритмы обработки сигналов SPIE, архитектуры и реализации XIII . Международное общество . дои : 10.1117/12.507012 .

[1]

[2]