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

Аппаратная конструкция умножителя

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

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

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

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

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

Описание

Пример схемы полного сумматора.

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

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

${\displaystyle d_{1}=2}$, и ${\displaystyle d_{j+1}=\operatorname {floor} (1.5d_{j}).}$

Это дает такую ​​последовательность:

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

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

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

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

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

4-слойное сокращение Дадда матрицы частичного произведения 8x8 с использованием 7 полусумматоров (две точки) и 35 полных сумматоров (три точки). Точки в каждом столбце — биты одинакового веса. Биты с меньшим весом — самые правые.

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

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

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

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

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

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

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

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

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

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

Добавление

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

Смотрите также

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

Ссылки

1. Дадда, Луиджи (май 1965 г.). «Некоторые схемы параллельных умножителей». Альта Фрекенца . 34 (5): 349–356.
   Dadda, L. (1976). "Некоторые схемы для параллельных умножителей". В Swartzlander, Earl E. (ред.). Computer Design Development: Principal Papers . Hayden Book Company. стр. 167–180. ISBN 978-0-8104-5988-5. OCLC  643640444.
2. Таунсенд, Уитни Дж.; Шварцлендер, младший, Эрл Э.; Абрахам, Джейкоб А. (декабрь 2003 г.). "Сравнение задержек умножителей Дадда и Уоллеса" (PDF) . SPIE Advanced Signal Processing Algorithms, Architectures, and Implementations XIII . Международное общество . doi :10.1117/12.507012.

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

• Savard, John JG (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc . Архивировано из оригинала 2018-07-03 . Получено 2018-07-16 .