Может ли кто-нибудь сказать разницу в метод или механизм частичного сокращения продуктов между множителями Уоллеса и Дадда?
Я читал A_comparison_of_Dadda_and_Wallace_multiplier_delays.pdf
Оба очень похожи. Вместо традиционного алгоритма, основанного на строках, все они нацелены на реализацию умножения 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 с более регулярной и реализуемой стратегией «разделяй и властвуй», как, например, множитель Лука-Вюйлемина.
Если мы конвейерируем эти сумматоры 4-2, сделает ли это структуру более привлекательной с точки зрения регулярности схемы, а также задержки (временной сложности) по сравнению с множителем переноса-сохранения массива?
Из Оптимальный по площади и времени целочисленный множитель СБИС с минимальным временем вычисления, почему множитель Luk-Vuillemin использует преобразование Фурье? Не усложнит ли это аппаратную реализацию?
WT регулярны, проблема заключается в глобальной взаимосвязи, которая приводит к нерегулярным структурам. Проблема их конвейеризации заключается в разной ширине. Традиционное «точечное» представление (как в вашем вопросе) маскирует тот факт, что все точки представляют информацию, которую необходимо передать на следующий этап. А ваша цифра как раз для мульта 8х8 бит. Вторая проблема, как сбалансировать время прохождения разных этапов? А целочисленные мультипликаторы 64x64 в современных процессорах имеют латентность 3 cy. Можно ли уменьшить его до 2? Возможно, но стоимость реализации очень высока.
Подождите, вы видели использование сумматора 4-2 для ЗАМЕНЫ дерева Уоллеса в моем предыдущем комментарии?
Luk-Vuillemin использует стратегию «разделяй и властвуй». Учитывая A=2^n/2xAh+Al, они считают, что AxB=2^nxAhxBh+2^n/2(AhxBl+AlxBh)+AlxBl. После рекурсивного применения они выполняют суммирование с помощью сумматоров CS. Стратегия генерации намного проще для понимания и реализации. А сложность аналогична мультам Уоллеса-Дадда.
Пропустил замену WT на 4-2 сумматора. Действительно, это более регулярно. Вы можете уменьшить на 2 количество бит для суммирования в 2 слоя. Однако у вас все еще есть некоторая неравномерность, потому что биты add расположены в виде трапеции, а не прямоугольника.
Как сложения получаются в форме трапеции?
Начальные колонны трапециевидные. Если бы все добавляемые столбцы были 8-битными, сокращение 4-2 было бы обычным. Но некоторые 7, 6, 5 и т.д.
Я немного смущен, «некоторые из них 7, 6, 5 и т. д.»?
Извините, я не был достаточно ясен. Это представляет количество битов в столбцах, которые необходимо подсчитать. Эти столбцы имеют форму трапеции (как в верхней левой части вашего рисунка), и это вносит некоторую неравномерность даже при обычной стратегии сокращения.
" Учитывая A=2^n/2xAh+Al, они считают, что AxB=2^nxAhxBh+2^n/2(AhxBl+AlxBh)+AlxBl. После рекурсивного применения этого они выполняют суммирование с сумматорами CS. " <= = это немного сбивает с толку, реальный числовой пример? Кстати, а откуда вы это процитировали? В ссылке pdf в моем предыдущем комментарии я видел только полиномиальное умножение.
Пусть 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
Я думаю, что это статья: Вуйлемин, Дж. (1983). Очень быстрый алгоритм умножения для реализации СБИС. Интеграция, о котором вы говорили?
Я также помню документ с Луком, который был, возможно, более подробным. Но идея абсолютно та же.
Вы имели в виду раздел 2 Рекурсивная реализация целочисленных множителей СБИС с оптимальным временем, но есть некоторые алгоритмы СБИС, такие как версии 4M, 3M и 2M? Вы когда-нибудь использовали что-нибудь из этого?
Кроме того, DADDA тоже неправильный? и если да, то почему так? Что вы думаете об использовании кодирование пары битов умножителя на сумматорах 4-2 или DADDA?
Кроме того, что касается 4-2 сумматора, все неполные биты располагаются ТОЛЬКО на двух уровнях. Почему вы утверждали, что «некоторым 7, 6, 5 и т. д.»?
Что вы думаете о рис. 39.5 (сумматор 4-2), благодаря которому дерево Уоллеса имеет правильную структуру?