Почему аппаратное деление занимает намного больше времени, чем умножение на микроконтроллере? Например, в dsPIC деление занимает 19 циклов, а умножение занимает только один такт.
Я прошел через некоторые учебники, в том числе алгоритм Дивизии и алгоритм умножения на Википедии. Вот мои рассуждения.
Алгоритм деления, как и метод медленного деления с восстановлением в Википедии, является рекурсивным алгоритмом. Это означает, что (промежуточные) результаты от шага k
используются в качестве входных данных для шага k+1
, что означает, что эти алгоритмы не могут быть распараллелены. Следовательно, n
для завершения деления требуются как минимум циклы, тогда n
как в бите делится количество битов. Для 16-разрядных дивидендов это равно как минимум 16 циклам.
Алгоритм умножения не должен быть рекурсивным, что означает, что его можно распараллелить. Тем не менее, существует много разных алгоритмов умножения, и я понятия не имею, какой из них может использоваться микроконтроллерами. Как работает умножение на аппаратном / микроконтроллере?
Я нашел алгоритм множителя Дадды , который должен занять всего один такт, чтобы закончить. Однако чего я не понимаю, так это того, что алгоритм Дадды выполняется в три этапа, тогда как результаты этапа 1 используются на этапе 2 и т. Д. В соответствии с этим для завершения потребуется по меньшей мере три такта.
источник
Ответы:
Разделитель гораздо менее элегантно сопоставляется с типичным оборудованием. В качестве примера возьмем ПЛИС решетки ICE40.
Давайте сравним два случая: этот множитель 8x8 и 16 бит:
и этот делитель, который уменьшает 8- и 8-битные операнды до 8-битного результата:
(Да, я знаю, часы ничего не делают )
Обзор сгенерированной схемы при отображении множителя на ПЛИС ICE40 можно найти здесь, а разделитель - здесь .
Статистика синтеза от Yosys:
умножить
делить
Стоит отметить, что размер сгенерированного verilog для множителя полной ширины и максимально делительного делителя не так уж и велик. Однако, если вы посмотрите на рисунки ниже, вы заметите, что множитель имеет, возможно, глубину 15, тогда как делитель выглядит примерно как 50 или около того; критический путь (т. е. самый длинный путь, который может возникнуть во время работы) определяет скорость!
Вы все равно не сможете прочитать это, чтобы получить визуальное впечатление. Я думаю, что различия в сложности можно обнаружить. Это множители / делители одного цикла!
Умножение
Умножьте на ICE40 (предупреждение: ~ 100 мегапиксельное изображение)
Делить
( Разделите на ICE40 ) (предупреждение: ~ 100-мегапиксельное изображение)
источник
Медленное деление по своей сути итеративное, поэтому оно занимает больше времени. Есть несколько более быстрые алгоритмы медленного деления, чем простые, использующие таблицы поиска. Алгоритм SRT производит два бита за цикл. Ошибка в такой таблице стала причиной печально известной ошибки Pentium FDIV (около 1994 г.). Тогда есть так называемые быстрые алгоритмы деления.
Конечно, в принципе, вы могли бы просто использовать огромную справочную таблицу для вычисления произведения или частного двух чисел и, таким образом, получить результаты за один цикл, но это быстро становится непрактичным по мере увеличения числа бит на число.
источник
Мы можем иметь несколько слоев логики за такт, но есть предел, сколько именно слоев логики у нас может быть, насколько сложными могут быть эти слои, будет зависеть от нашей тактовой частоты и нашего полупроводникового процесса.
На самом деле большинство умножения в компьютерах использует вариант двоичного длинного умножения. Двоичное длинное умножение включает в себя
Итак, давайте посмотрим на реализацию этого в оборудовании.
Итак, давайте рассмотрим, сколько логических этапов нам нужно для умножителя 8x8 с 16-битными результатами. Для простоты предположим, что мы не пытаемся оптимизировать тот факт, что не во всех промежуточных результатах есть биты во всех позициях.
Предположим, что полный сумматор реализован в двух «этапах гейта».
Всего около 46 логических этапов. Большая часть которых потрачена на суммирование двух последних промежуточных результатов.
Это может быть улучшено еще больше, если использовать тот факт, что не во всех промежуточных результатах присутствуют все биты (это, в основном, то, что делает множитель Дада), используя сумматор с переносом данных на последнем этапе. Добавляя 7 чисел, получим 3 вместо трех, чтобы произвести две (уменьшение количества ступеней за счет увеличения количества ворот и более широких ворот) и т. Д.
Это все второстепенные детали, однако, важный момент заключается в том, что количество этапов, необходимых для умножения двух n-битных чисел и получения 2-битного результата, примерно пропорционально n.
С другой стороны, если мы посмотрим на алгоритмы деления, мы обнаружим, что все они имеют итерационный процесс, где.
Таким образом, число логических этапов, необходимых для реализации деления, примерно пропорционально n в квадрате.
источник
Алгоритм деления (фактически любой алгоритм) может быть выполнен за один такт. Если вы готовы платить за дополнительные транзисторы и снизить допустимую тактовую частоту.
Предположим, у вас есть набор вентилей, который реализует один тактовый цикл существующего алгоритма деления на несколько циклов. Чтобы сделать алгоритм единичным циклом, используйте несколько этапов аппаратного обеспечения (аналогично тому, что использовалось на одном этапе многоциклового алгоритма), с выводом одного этапа, подающего следующий этап.
Конечно, причина не делать это таким образом, что он использует много транзисторов. Например, для 16-битного деления он может использовать почти в 16 раз больше транзисторов. Кроме того, наличие большего количества ступеней затворов снижает максимально допустимую тактовую частоту (поскольку имеется больше ступеней задержки распространения).
источник
Практические алгоритмы деления основаны на числовых наборах, которые сходятся к частному.
Существуют аддитивные методы, такие как невосстановление или СТО, которые работают путем добавления или удаления 2 ^ N к частному и, соответственно, добавления или удаления делителя 2 ^ N * к частичному остатку до тех пор, пока он не достигнет нуля.
Существуют мультипликативные методы, такие как метод Ньютона-Рафсона или Гольдшмана, которые являются методами поиска корней, где деление вычисляется как обратное умножению.
Аддитивные методы дают один или несколько битов за цикл. Мультипликативные методы удваивают число битов для каждого цикла, но требуют некоторого начального приближения, часто получаемого с помощью таблицы констант.
«Медленные» и «быстрые» номиналы вводят в заблуждение, так как фактическая скорость зависит от количества битов, от того, сколько оборудования выделено для функции (а быстрый множитель очень велик) ...
Деление медленнее, чем умножение, потому что нет прямого, параллельного метода для его вычисления: либо существует итерация, либо аппаратное обеспечение копируется для реализации итерации в виде каскадных (или конвейерных) блоков.
источник
Это не вопрос электроники. В лучшем случае это компьютерный вопрос, лучше адресованный Stack Overflow.
См., Например, здесь: Является ли умножение быстрее, чем деление с плавающей точкой?
В действительности это вопрос из реальной жизни: почему деление занимает намного больше времени, чем умножение?
Что бы вы предпочли посчитать на бумаге?
или
Деление занимает больше времени, чем умножение, потому что это сложнее сделать .
источник