Различия между деревом Уоллеса и множителями Дадда

Может ли кто-нибудь сказать разницу в метод или механизм частичного сокращения продуктов между множителями Уоллеса и Дадда?

Я читал A_comparison_of_Dadda_and_Wallace_multiplier_delays.pdf

Различия между деревом Уоллеса и множителями Дадда

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
4
0
1 759
1

Ответы 1

Оба очень похожи. Вместо традиционного алгоритма, основанного на строках, все они нацелены на реализацию умножения A*B на 1/и умножение A на биты b_i, 2/подсчет битов для каждого столбца до тех пор, пока не останется только две строки, и 3/выполнение окончательного сложения с быстрым сумматор.

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

Уоллес представил структуру «дерева Уоллеса» (которая до сих пор полезна в некоторых проектах). Это позволяет, учитывая n битов, подсчитать количество битов в 1 в этом наборе. Дерево Уоллеса (n,m) (где m=ceil(log_2 n)) дает количество битов в 1 среди n входных данных и выводит результат в m битах. Это своего рода комбинаторный счетчик. Например, ниже приведена схема (7,3) дерева Уоллеса, сделанного с полными сумматорами (то есть (3,2) деревьями Уоллеса).

Как видите, это дерево генерирует результаты логического веса 2^0, 2^1 и 2^2, если входные биты имеют вес 2^0.

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

Луиджи Дадда не использует такую ​​агрессивную стратегию уменьшения и старается сделать высоту столбцов более сбалансированной. Используются только полные (или половинные) сумматоры, и каждый счет/сокращение будет генерировать только биты веса 2^0 и 2^1. Процесс сокращения менее эффективен (что видно по большему количеству строк на вашем рисунке), но количество ворот лучше. Стратегия Дадда также должна была быть немного менее эффективной по времени, но, судя по приложенному документу, которого я не знал, это неправда.

Основной интерес к Множители Уоллеса/Дадда заключаются в том, что они могут достичь умножения с временной сложностью ~ log n, что намного лучше, чем традиционный множитель массива O (n) с сумматорами с сохранением переноса. Но, несмотря на это теоретическое преимущество, в действительности они больше не используются. Существующие архитектуры больше заботятся о пропускной способности, чем о задержке, и предпочитают использовать более простые структуры массивов, чем те, которые могут быть эффективно конвейеризированы. Реализация структуры Wallace/Dadda — это настоящий кошмар, если не считать нескольких битов, а добавление конвейера к ним очень сложно из-за их неправильной структуры.

Обратите внимание, что другие конструкции множителей уступают временной сложности log n с более регулярной и реализуемой стратегией «разделяй и властвуй», как, например, множитель Лука-Вюйлемина.

Что вы думаете о рис. 39.5 (сумматор 4-2), благодаря которому дерево Уоллеса имеет правильную структуру?

kevin998x 27.01.2019 06:46

Если мы конвейерируем эти сумматоры 4-2, сделает ли это структуру более привлекательной с точки зрения регулярности схемы, а также задержки (временной сложности) по сравнению с множителем переноса-сохранения массива?

kevin998x 27.01.2019 06:58

Из Оптимальный по площади и времени целочисленный множитель СБИС с минимальным временем вычисления, почему множитель Luk-Vuillemin использует преобразование Фурье? Не усложнит ли это аппаратную реализацию?

kevin998x 27.01.2019 08:17

WT регулярны, проблема заключается в глобальной взаимосвязи, которая приводит к нерегулярным структурам. Проблема их конвейеризации заключается в разной ширине. Традиционное «точечное» представление (как в вашем вопросе) маскирует тот факт, что все точки представляют информацию, которую необходимо передать на следующий этап. А ваша цифра как раз для мульта 8х8 бит. Вторая проблема, как сбалансировать время прохождения разных этапов? А целочисленные мультипликаторы 64x64 в современных процессорах имеют латентность 3 cy. Можно ли уменьшить его до 2? Возможно, но стоимость реализации очень высока.

Alain Merigot 27.01.2019 08:22

Подождите, вы видели использование сумматора 4-2 для ЗАМЕНЫ дерева Уоллеса в моем предыдущем комментарии?

kevin998x 27.01.2019 08:29

Luk-Vuillemin использует стратегию «разделяй и властвуй». Учитывая A=2^n/2xAh+Al, они считают, что AxB=2^nxAhxBh+2^n/2(AhxBl+AlxBh)+AlxBl. После рекурсивного применения они выполняют суммирование с помощью сумматоров CS. Стратегия генерации намного проще для понимания и реализации. А сложность аналогична мультам Уоллеса-Дадда.

Alain Merigot 27.01.2019 08:30

Пропустил замену WT на 4-2 сумматора. Действительно, это более регулярно. Вы можете уменьшить на 2 количество бит для суммирования в 2 слоя. Однако у вас все еще есть некоторая неравномерность, потому что биты add расположены в виде трапеции, а не прямоугольника.

Alain Merigot 27.01.2019 08:39

Как сложения получаются в форме трапеции?

kevin998x 27.01.2019 08:46

Начальные колонны трапециевидные. Если бы все добавляемые столбцы были 8-битными, сокращение 4-2 было бы обычным. Но некоторые 7, 6, 5 и т.д.

Alain Merigot 27.01.2019 08:59

Я немного смущен, «некоторые из них 7, 6, 5 и т. д.»?

kevin998x 27.01.2019 09:43

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

Alain Merigot 27.01.2019 10:10

" Учитывая A=2^n/2xAh+Al, они считают, что AxB=2^nxAhxBh+2^n/2(AhxBl+AlxBh)+AlxBl. После рекурсивного применения этого они выполняют суммирование с сумматорами CS. " <= = это немного сбивает с толку, реальный числовой пример? Кстати, а откуда вы это процитировали? В ссылке pdf в моем предыдущем комментарии я видел только полиномиальное умножение.

kevin998x 27.01.2019 12:50

Пусть T(N) — время a AxB, где A и B — n бит. Предположим, вы вычисляете AxB=2^nxAhxBh+2^n/2(AhxBl+AlxBh)+AlxBl. Все множения на полуслова выполняются параллельно и требуют времени T(n/2). Если добавления выполняются с помощью CSA, это занимает время O(1). Отсюда T(n)=T(n/2)+O(1) и T(n)=log n. В настоящее время у меня нет бумаги Лука-Вюйлемена. Может быть, в пыльной стопке бумаг в моем офисе. Это старая статья, но ее можно найти в Интернете. Я не знаю Люка, но вы можете отправить письмо Жану Вюймену di.ens.fr/~jv

Alain Merigot 27.01.2019 13:06

Я также помню документ с Луком, который был, возможно, более подробным. Но идея абсолютно та же.

Alain Merigot 27.01.2019 13:35

Вы имели в виду раздел 2 Рекурсивная реализация целочисленных множителей СБИС с оптимальным временем, но есть некоторые алгоритмы СБИС, такие как версии 4M, 3M и 2M? Вы когда-нибудь использовали что-нибудь из этого?

kevin998x 28.01.2019 03:25

Кроме того, DADDA тоже неправильный? и если да, то почему так? Что вы думаете об использовании кодирование пары битов умножителя на сумматорах 4-2 или DADDA?

kevin998x 28.01.2019 04:33

Кроме того, что касается 4-2 сумматора, все неполные биты располагаются ТОЛЬКО на двух уровнях. Почему вы утверждали, что «некоторым 7, 6, 5 и т. д.»?

kevin998x 28.01.2019 05:23

Другие вопросы по теме