Алгоритм умножения на логических схемах

Для быстрых вычислений (1 такт), используют https://en.wikipedia.org/wiki/Booth's_multiplication_algorithm

Для экономии логики используют описанный алгоритм со сдвигами.

То, что предложено тут не масштабируется. Критический параметр в комбинаторных схемах - это глубина уровней логики. Так как в реальных элементах есть задержка, то максимальная производительность зависит от того, через сколько логических элементов проходят входные сигналы до достижения выходов.

имеет ли смысл подобное реализовывать в софт-микропроцессорах?

Да, если ты умножаешь только числа разрядностью три бита. А ещё лучше два бита. Если больше, то требуемое количество логических элементов у тебя растёт как n в какой-то безумной степени.

И да, есть ли в Verilog или VHDL cредства для кодогенерации того, что я тут изобразил, для произвольной разрядности чисел?

Есть generate, если очень хочется и не жаль отдать всю плисину под умножитель.

Так как в реальных элементах есть задержка, то максимальная производительность зависит от того, через сколько логических элементов проходят входные сигналы до достижения выходов.

В этой схеме их как раз немного. Больше будет длина линий влиять, так как размер всей схемы будет огромным.

Не стал всматриваться сильно, но я так понимаю, что ты придумываешь известное решение - матричный умножитель (ищи в гугле). Это решение подходит для операндов небольшой разрядности. Как только начинаешь расширяться, то начинают быстро расти аппаратурные затраты. Поэтому дальше используют другие методы (например, метод Бута, дерево Уоллеса).

Не стал всматриваться сильно, но я так понимаю, что ты придумываешь известное решение - матричный умножитель

Нет. В матричном умножителе используется сумматор. У меня сумматора нет

Нет. В матричном умножителе используется сумматор. У меня сумматора нет

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

UPD: просто используя многовходовые ЛЭ. но сути это не меняет. Скорее всего, схемы просто эквивалентны.

Нет там сумматоров. Сумматор, если что, изображен у меня на аватарке. Там такого не используется

Нет, это не матричный умножитель. Это LUT на 2^(2n) значений.

Я как раз тебе хотел схему сумматора скинуть.

Надо проверить эквивалентность. Одну и туже комбинационную функцию можно реализовать по-разному.

Логическая эквивалентность-то там будет (и то, и другое — сумматор, всё-таки). Но схема в сабже жрёт совершенно анекдотическое количество логики по сравнению с матричным сумматором и имеет меньший critical path (потому что не требует переноса разрядов, как сумматоры).

Ну для уменьшения числа элементов существует минимизация. Сейчас это сделано просто вручную. Классические схемы сумматоров просто разрисованы в более простых элементах, чтобы показать, как устроен один примитивный сумматор. Но если выложить матрицу сумматоров и разрисовать ее полностью в ЛЭ, то потом эта схема может быть с успехом минимизирована автоматически. Выбор базовых логических функций богат. По идее, САПР должен с этим справиться. Можно, кстати, для интереса сравнить затраченные ресурсы в обоих случаях.

Сумматор, если что, изображен у меня на аватарке. Там такого не используется

Да, к слову, у тебя на аватарке все-таки двухразрядный сумматор. Одноразрядный сумматор с переносом, который в канонических схемах матричных умножителей используются, попроще. Да и мало их будет для умножения 3x3 (сколько? шесть, по-моему, всего?)

Ну вот собственно сделал умножение 3x3 через сумматоры: https://i.imgur.com/9JCy2D2.png http://dump.bitcheese.net/files/ilucici/mult_adder.circ
Глубина уровней логики (если я правильно понимаю этот термин) получилась больше

Логическая эквивалентность-то там будет (и то, и другое — сумматор, всё-таки)

Нет в исходной схеме никаких сумматоров. Если есть - ткните пальцем

Ты в институте учил дискретку? Минимизацию делал хоть раз вручную на бумажке (см. минимизация булевых функций)? Я тебя уверяю 100%, что твоя схема - это просто минимизированный вручную по догадке (молодец) матричный сумматор. Твой САПР все методы минимизации использует на полную катушку. Вот ты собери проект под какой-нибудь кристалл и сравни ресурсы, задержки твоей схемы и канонической.

То, что ты разрисовал, нарисовано в элементах, в которых в учебниках рисуют одноразрядные сумматоры без использования многовходовых ЛЭ. Поэтому эти схемы и не будут похожи с самого начала. А после минимизации будут.

Ты в институте учил дискретку? Минимизацию делал хоть раз вручную на бумажке (см. минимизация булевых функций)?

Нет, дискретку я по интернету учил. У меня образование по другому профилю. Минимизацию я вручную сделать осилю

Я тебя уверяю 100%, что твоя схема - это просто минимизированный вручную по догадке (молодец) матричный сумматор.

Нет, эта схема по сути своей является таблицей поиска, сокращенной в два раза за счет того, что умножение коммутативно. Насчет минимизации: если требуется решить задачу с использованием минимума логических элементов, то тут минимизации никакой нет: можешь посчитать логические элементы в исходной http://dump.bitcheese.net/images/aditoso/sc.png и только что мной сделанной https://i.imgur.com/9JCy2D2.png схеме. В исходной схеме логических элементов значительно больше. Но с другой стороны исходная схема «быстрее». Принцип ее работы можно сравнить с функциональными трубками, см. http://www.155la3.ru/lf.htm
Это такая таблица поиска, реализованная на аппаратном уровне. По смыслу это близко к https://en.wikipedia.org/wiki/Programmable_logic_array
Вот один из ранних вариантов https://i.imgur.com/jgRm2TZ.png когда я это пытался изобразить по аналогии с таблицей пифагора

Описался, да. Имел в виду «и то, и другое — умножитель».

Пффф, ну нет же, ну! Ну у тебя твоя комбинационная функция реализует ту же самую функцию, что и матричный сумматор. Они *одинаковые*. В НИИ, когда компьютеры были большими, такие функции яйцеголовые просто вручную минимизировали, делая меньше уровней. Но функция той же и остается. Сейчас это делает САПР. Алгоритм там продвинутые. Машина должна страдать, а человек думать.

Если ты не поленишься и выберешь правильную оптимизацию, то САПР даже может лучше тебя это дело заоптимизировать в соответсвии с тем, что на борту у кристалла. А как только ты перейдешь к более сложным вариантам, то твои возможности резко станут хуже по сравнению с машиной.

можешь посчитать логические элементы в исходной http://dump.bitcheese.net/images/aditoso/sc.png и только что мной сделанной https://i.imgur.com/9JCy2D2.png схеме.

Еще раз - считать ничего не надо. После минимизации число элементов *меняется*, могут появиться многовходовые элементы вместо двухвходовых и т. д.

Вот тебе пример процессов в самых простых примерах. http://kit-e.ru/articles/plis/2008_5_148.php

Ты можешь даже задавать свой умножитель 3 на 3 таблицей истинности (огромная будет, да). Это одно и то же: таблица истинности и две схемы эквивалентны, просто ты реализовал ту же функцию, но более минимально, поэтому ты не узнаешь сумматоров. Разумеется, так все всегда и делают - минимизируют булевы функции. У одних дома только К155ЛА3 лежит, поэтому может только в базисе штрих Шеффера (при помощи только штриха Шеффера, то есть ЛА3 ты можешь реализовать любую вообще булеву функцию - тем и примечательна К155ЛА3 :). А у другого есть еще 6И-НЕ или, там, 8ИЛИ. И тогда может получиться булеву функцию переписать так, что, число уровней начинает схлопываться.

Это же и делает компилятор. Функция у тебя такая же, как и у матричного умножителя. Компилятор посмотрит на доступный базис на кристалле и перепишет все это хозяйство в соответствии с твоими критериями (одному меньше места надо, другому скорость важна). Если скажешь ему «минимизируй время», то он минимизирует все схемы и таблицу истинности так, чтобы было минимальное число уровней прохождения сигнала. Должен, по крайней мере.

Ты можешь даже задавать свой умножитель 3 на 3 таблицей истинности (огромная будет, да).

Да, я могу из любой таблицы истинности сделать такую штуку. Могу даже написать программу, которая по таблице истинности такое будет строить. Ибо эта штука - таблица поиска.
А вот в силу компиляторов я не верю. Не знаю насчет компиляторов из верилога в топологию FPGA, но компиляторы из Си в ассемблер x86-64 (clang, gcc) справляются хуже, чем человек

Это легко проверить, не отходя от кассы. Компиляция и отчет компиляции. Симуляция. Результаты были бы, наверное, многим интересны. Твою же схему САПР тоже будет переобдумывать, когда будет укладывать в кристалл.

Не знаю насчет компиляторов из верилога в топологию FPGA

первым делом он отобразит твою схему на элементную базу целевого кристалла. 2-входовые логические функции будут упрессованы в 4-6-входовые и т.д. от схемы рожки да ножки останутся

Ну что ты распинаешься, человек «неверит». Про минимизацию по критериям не слышал, об энергопотреблении не думал. О том что иногда дешевле сделать готовые таблицы похоже тоже не знает.

Я вместо «верить-неверить» предпочитаю экспериментальную проверку и доказательства. Вера это для всяких там религиозниковю.

Да, кстати, есть ли декомпиляторы FPGA-топологий? Ну чтоб примерно как HEX-rays чтобы переводилось в некий более-менее человекочитаемый код.

Тогда вернись к истокам. Раз уж лабы тебе недоступны, как они там ныне не знаю, но в прошлом веке студенты собирали всю логику на разной элементной базе, то пиши симуль и проверяй свои схемы, благо они не сложные. Подобные симуляторы так же писались студентами на старших курсах, весьма полезное занятие, перед переходом к плис

в прошлом веке студенты собирали всю логику на разной элементной базе

Ну вообще-то я могу накупить элементной базы и спаять из нее логику...

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

А зачем писать свой симуль? Во-первых я могу сразу код на С написать, который будет эмулировать мою схему, без всяких там симулей. Вот например я ради развлечения писал двоичный сумматор на си вручную:

#include <inttypes.h>
#include <stdio.h>
 
typedef union
{
  struct
  {
    #define BITG(n) uint8_t bit##n : 1
    BITG(0);
    BITG(1);
    BITG(2);
    BITG(3);
    BITG(4);
    BITG(5);
    BITG(6);
    BITG(7);
    #undef BITG
  } bits;
  uint8_t value;
}getbit;
 
uint8_t bit_sum(uint8_t, uint8_t);
 
 
uint8_t bit_sum(uint8_t a, uint8_t b)
{
  getbit op1, op2, opr;
  uint8_t carry;
  op1.value=a; op2.value=b;
  #define OP1(n) op1.bits.bit##n
  #define OP2(n) op2.bits.bit##n
  #define OPR(n) opr.bits.bit##n
  #define XOR(a,b) ((a)^(b))
  #define AND(a,b) ((a)&(b))
  OPR(0) = XOR(OP1(0), OP2(0));
  carry = AND(OP1(0), OP2(0));
  #define SETBIT(n)                \
  OPR(n) = XOR                     \
           (                       \
             carry,                \
             XOR(OP1(n), OP2(n))   \
           );
 
  #define CARRYBIT(n)              \
  carry = XOR                      \
          (                        \
            AND(OP1(n), OP2(n)),   \
            AND                    \
            (                      \
              XOR(OP1(n), OP2(n)), \
              carry                \
            )                      \
          );
  SETBIT(1);
  CARRYBIT(1);
  SETBIT(2);
  CARRYBIT(2);
  SETBIT(3);
  CARRYBIT(3);
  SETBIT(4);
  CARRYBIT(4);
  SETBIT(5);
  CARRYBIT(5);
  SETBIT(6);
  CARRYBIT(6);
  SETBIT(7);
  return opr.value;
  #undef SETBIT
  #undef CARRYBIT
  #undef OP1
  #undef OP2
  #undef OPR
  #undef XOR
  #undef AND
}
 
int main (int argc, char *argv[], char *envp[])
{
  uint8_t a, b, c;
  scanf ("%"SCNu8"%"SCNu8, &a, &b);
  c = bit_sum(a,b);
  printf("%"PRIu8"\n", c);
  return 0;
}

Требуется чтоб симуль повторял работу схемы логического элемента, от выбора элементной базы, будет зависеть очень много параметров - время распространения сигнала, нагрузочная способность входов выходов, энергопотребление. Все это нужно для понимания, как оптимизируется схема в FPGA. spice тебе в помощь

он вроде что-то на спартанах там делает

«Дяденька, я не настоящий сварщик, а маску я на стройке нашел».

Насчет того что вы предлагаете у меня две мысли: 1. Думаю, не сложно написать формулу, которая будет связывать разрядность чисел и кол-во логических элементов (именно по приведенной логике). И оттуда же будет следовать количество уровней и кол-во связей. Можно быстро в лоб посчитать для минимальной разрядности операндов (2-3-4), а потом «догадаться» формулу. Уверен там будет степенная функция, и после подстановки например 32-операндов, получится схема которая не в каждый «триллионник» (это я сам придумал, таких плисин еще не изобрели) влезет (без оптимизации). в целом это мне очень напоминает разложение на простые множители чисел. Точней все к этой задаче в конце концов и сведется.

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

В качестве домашнего задания (вы же «предпочитаю экспериментальную проверку и доказательства». ), посчитайте кол-во линий для «одноединичного» кода для 32 разрядных операндов и кол-во элементов для дешифратора. А потом прикиньте какой максимальной разрядности умножитель можно уместить в «миллионник».

1. Думаю, не сложно написать формулу, которая будет связывать разрядность чисел и кол-во логических элементов (именно по приведенной логике). И оттуда же будет следовать количество уровней и кол-во связей. Можно быстро в лоб посчитать для минимальной разрядности операндов (2-3-4), а потом «догадаться» формулу.

Дело в том, что формула эта должна учитывать, сколько чисел могут быть получены при умножени n-разрядных чисел. А чтобы узнать, сколько именно чисел может быть получено при перемножении n-разря.. Короче, там в этой формуле как минимум будет фигурировать https://ru.wikipedia.org/wiki/Функция_распределения_простых_чисел и «догадаться» формулу тут не получится. Т.е. оно зависит от количества простых чисел, меньших чем произведение 0xFFFF... * 0xFFFF... .

2. Вся эта дискретная логика давно разработанный матаппарат, что-то новое в этом открыть, лично мне кажется, уже безнадежным

Дискретная логика это всего лишь еще один «язык программирования», новые алгоритмы постоянно изобретают, и постоянно открывают что-то новое. Насчет компилирования из verilog в топологию FPGA - тут тоже есть над чем подумать. Я вот например ковырял компилятор GCC на всяких синтетических примерах, и нашел много глупостей, которые этот компилятор делает. Вот например https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68027
Уверен что и компиляторы verilog тоже кучу глупостей делают в своих оптимизаторах, просто никто на детальные «ковыряния» не тратит времени. Работает - ну и отлично.
Кстати, есть ли опенсорсные компиляторы из verilog в какую-нибудь ПЛИС-ину. Хочу алгоритмы исследовать

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

Дык вот уже готовые формулы для оценок.

Дискретная логика

Описался, имелась ввиду дискретная математика. Там уже все есть. Сейчас можно только выжимать единицы и доли процентов эффективности для частных случаев.

новые алгоритмы постоянно изобретают, и постоянно открывают что-то новое

Никто, не спорит. Только вы обратите внимание на их эффективность и применимость в сравнении с другими алгоритмами.

Думать, что человек может с оптимизировать лучше алгоритма, печальное заблуждение. Компутер железный, он может тупо перебрать все возможные варианты. Вы в курсе, что компутер в шахматы сейчас играет лучше человека причем довольно давно и человеку уже компутер не догнать? Так что, если вы нашли, где-то косяк в компиляторе, то это всего лишь проблема пограмиста который это место писал. Это проблема не в алгоритмах, а в реализации (потому как их пишет белковая субстанция).

Я вот например ковырял компилятор GCC на всяких синтетических примерах, и нашел много глупостей, которые этот компилятор делает.

Ничего не скажу за GCC, но думается мне, что все на так однозначно. Если ваш патч примут в GCC можно говорить о «нашел много глупостей», в противном случае это просто надувание пузырей соплями.

Кстати, есть ли опенсорсные компиляторы из verilog в какую-нибудь ПЛИС-ину. Хочу алгоритмы исследовать

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

Вы, кстати, домашнюю работу не сделали. Без этого продолжать общение, считаю бессмысленным.

И зачем ОП кастанул этого эффективного менеджера. Ни разу не видел от него вразумительного поста, один сарказм и смишнявочки.

Я находил, кстати, пример какого-то вериложного синтезатора от человека, причастного к иверилогу, когда искал тул для визуализации схемы. Софтинка обещала генерить файлик плисонезависимый, то есть без использования фич того или иного вендора.

Это потому что он рассказывал что-то про разработку на ПЛИС Разработка сложных радиоэлектронных устройств а еще в одном треде говорил про Spartan-ы защита исполняемого файла от нелицензионного запуска (комментарий) вот я его и приметил. Но вообще да, видимо зря я его кастанул. Какие-то домашние задания мне еще предлагает делать... У меня есть дела поважнее. Хотя ради интереса может и сделаю, только вот в виде обычной формулы это сделать не получится, а вот решение в виде кода - вполне.

Любая комбинационная схема является таблицей поиска. Вообще любая.

эффективного менеджера

ви мне льстите :)))

Похоже тут скоро у меня появится секта из анонимусов.

http://www.clifford.at/yosys/about.html

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

Я пытаюсь вас аккуратно подтолкнуть к идее, что прежде чем писать код, нужно на бумажке посчитать, что вообще должно получиться, к чему стремиться и какие ресурсы потребуются. Причем расчет это на полминуты с карандашом, а если калькулятор будет то и за 10 сек. можно управиться (это к вопросу что важней).

Но если вам плевать на теорию и важней решение в виде кода. Тогда извините, я пошел обедать.

А как по-вашему должна выглядеть формула, которая бы показывала количество чисел, которые могут быть получены путем умножения двух n-битных чисел?

Ту часть, которая волнует ТСа (отображение таблицы на LUTы поменьше или фиксированную логику) там делает ABC, которую можно и отдельно от yosys погонять.

Вполне может быть, я не разбирался. Спасибо за информацию.

Да, там еще надо находить множество способов представить число a как произведение неких двух действительных чисел b * c причем b и c должны быть не больше чем 2^n

с заявлением

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

я не согласен. Эта задача на теорию чисел, и она не является элементарной для людей, незнакомых с этой областью

А как по-вашему должна выглядеть формула, которая бы показывала количество чисел, которые могут быть получены путем умножения двух n-битных чисел?

Мдя.

Ладно уж, сделаю вашу домашку за вас (чтобы анонимусы не обвиняли в пустопорожнем сарказме и смешнявках).
Начну с того что в целом я согласен с ораторами которые вам отвечали в самом начале, всю ночь напролет (Зубок и компания), уже на этом этапе можно было забросить вашу идею.
Я же предложил рассчитать отдельные части вашего умножителя для случая 32-разрядных чисел. Вашу схему можно условно разделить на 3 части:
1. дешифратор в одноединичный код
2. «шифратор» всевозможных результатов в выходное значение.
3. «линии связи» между дешифратором и «шифратором» .
Как было уже замечено сложность шифратора пропорциональна количеству всех чисел получающихся при перемножении. Воспользуемся комбинаторикой. У нас есть два набора чисел от 0 до 2^32. сколькими способами можно из них выбрать пары (те самые произведения)? Если пока не заморачиваться повторами то это будет просто произведение кол-ва чисел. Итого 2^64. Можно конечно отсюда отсечь варианты с перестановкой множителей, разделим на 2. Получим 2^63 это конечно все меняет. Вот пропорционально этому числу у нас и будет размер нашего «шифратора». Допустим каждое число мы можем таким образом «зашифровать» с помощью 2 логических элементов. Вот вам и сложность шифратора: 2*2^63.
Теперь по линиям связи. Чтобы представить два 32-числа. Нам нужно 2 * 2^32 линий. Вроде просто. При этом мы не учитываем связи между логическими элементами.
Теперь дешифратор. Для 3-х двоичных разрядов нам нужно 8 логических элементов плюс 3 инвертора. Если мы хотим увеличит дешифратор на единицу, то понадобиться уже... фиг знает. Но как минимум нужен один логический элемент к которому будет приходить «линия связи». То есть на два операнда как минимум 2*2^32 логических элементов.
Ну вот и давайте оценим по минимуму что получилось:
логических элементов: 2*2^63 + 2*2^32
линий связи между этими блоками : 2 * 2^32
А теперь переведем это в доступные нам десятичные числа:
2*9*10^18+2*4*10^9 = примерно охулиярд логических элементов.
линий чуток поменьше всего ~8 млрд.
Теперь расскажите как все это засунуть в самую жирную плисину?

Ну и насчет формулы:
получается она примерно такая (для кол-ва логических элементов): 2*2^(2n-1)+2*2^n. Понятно, что она не точная, но порядок именно такой. Можно из нее прикинуть сколькиразрядный умножитель влезет в миллион логических элементов. По моим прикидкам уже для 10 разрядов получается больше 2-х млн.

Понятно, что она не точная, но порядок именно такой.

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

Ну вы б тогда уточнили, что нужна примерная, а не точная формула для вычисления количества логических элементов.

А разве не очевидно, что для первоначальной оценки потребных ресурсов точность в 10% вполне допустима?

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

Ладно, вы все еще настаиваете на своем алгоритме?

Ладно, вы все еще настаиваете на своем алгоритме?

Я полагаю что он вполне применим для чисел малой размерности. А для перемножения больших чисел лучше использовать другие схемотехнические решения

Я полагаю что он вполне применим для чисел малой размерности.

Ну хоть что-то.
Осталось скачать любую среду проектирования (от хилых или альтеры), загнать туда визард умножителя 3х3 и получить точно такую же схему, что и в заголовке. И мы опять вернемся к тому, что сказал Зубок.

...Уф, надо было поспать, а то работы привалило, а я как дурак, зацепился за твою тему, а уже утро настало.

Я глянул исходную схему чуть-чуть повнимательнее. А ты проверил - она работает? А то я на глаз что-то не могу определить.

Ты свел произведение двух 3-битных чисел к произведению двух 7-битных чисел, у которых только всего одна единица в каком-то разряде. На самом деле, ты построил специализированный умножитель 7-битных чисел специального вида, у которых всего одна единица в разрядах. Таким образом, каскады сумматоров у тебя полностью выродились. Вырожденный умножитель получился просто. По краям ты обставил эти числа дешифратором и шифратором.

Теперь мнение по практичности. Непрактично совершенно. Если ты будешь множить 8-битные числа, то сам прикинь, сколько у тебя ресурсов сожрет твое решение. Уже сразу два дешифратора 8 в 256, а что там дальше по схеме получится, даже представлять не хочется. :)

А ты проверил - она работает.

Должно работать. На входе два комплекта цифирь. На пересечении значения умножений с оптимизацией для одинаковых результатов (типа 3*4 и 1*6). Правда дешифратор не полный (должно быть 8 выходов, а не 7, ну это не самая главная проблема). Потом эти отдельные числа обратно шифруются в 6 битный код.