Оба очень похожи. Вместо традиционного алгоритма, основанного на строках, все они стремятся реализовать умножение 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. Процесс сокращения менее эффективен (как видно по большему количеству строк на фигуре), но количество гейтов лучше. Стратегия Dadda также должна была быть немного менее эффективной по времени, но согласно приложенному документу, который я не знал, это неправда.
Основной интерес в
Умножители Уолласа и Дадды заключаются в том, что они могут достичь умножения с ~ log n временной сложностью, что намного лучше, чем традиционный умножитель массивов O (n) с сумматорами сохранения переноса. Но, несмотря на это теоретическое преимущество, они больше не используются. Существующие архитектуры больше заботятся о пропускной способности, чем о задержке и предпочитают использовать более простые структуры массива, чем может быть эффективно передано по конвейеру. Реализация структуры Уоллеса / Дадды - настоящий кошмар за несколько битов, и добавление к ним конвейера очень сложно из-за их нерегулярной структуры.
Обратите внимание, что другие конструкции умножителей дают возможность регистрировать n временных сложностей с более регулярной и реализуемой стратегией "разделяй и властвуй", как, например, множитель Лука-Вуйемина.