Почему аппаратное деление занимает намного больше времени, чем умножение?

37

Почему аппаратное деление занимает намного больше времени, чем умножение на микроконтроллере? Например, в dsPIC деление занимает 19 циклов, а умножение занимает только один такт.

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

Алгоритм деления, как и метод медленного деления с восстановлением в Википедии, является рекурсивным алгоритмом. Это означает, что (промежуточные) результаты от шага kиспользуются в качестве входных данных для шага k+1, что означает, что эти алгоритмы не могут быть распараллелены. Следовательно, nдля завершения деления требуются как минимум циклы, тогда nкак в бите делится количество битов. Для 16-разрядных дивидендов это равно как минимум 16 циклам.

Алгоритм умножения не должен быть рекурсивным, что означает, что его можно распараллелить. Тем не менее, существует много разных алгоритмов умножения, и я понятия не имею, какой из них может использоваться микроконтроллерами. Как работает умножение на аппаратном / микроконтроллере?

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

Марко Гулин
источник
2
Алгоритм на самом деле не определяет количество тактов. Ваш конкретный процессор может иметь аппаратный множитель / делитель, работающий за один цикл или 20 циклов, независимо от внутренней реализации.
Евгений Ш.
1
OP, можете ли вы предоставить ссылку, которая дает больше информации о 19 против 1 циклах, о которых вы говорите? Что-то конкретное в вашем DSP.
Владимир Краверо
1
Спасибо за ответы. Вот таблица данных для моего микроконтроллера: ww1.microchip.com/downloads/en/DeviceDoc/70005127c.pdf . См. Обзор набора инструкций, начиная со страницы 292. В нем говорится, что все инструкции DIV занимают 18 циклов, в то время как все инструкции MUL занимают только 1 цикл. Но это не распространено только для этого MCU, я видел это во многих других MCU.
Марко Гулин
2
@ Конечно, они примерно одинаковые, не так ли? Для меня. Я не думаю, что это иллюстрирует так хорошо, как вы можете себе представить.
TonyM
1
Другим фактором является экономика и модели использования. Большинство случаев использования умножают гораздо чаще, чем делят. Выделение большой площади кремния для более быстрой аппаратной функции разделения, которая будет использоваться относительно редко, является плохой экономикой. Лучше сделать меньший и более дешевый чип или использовать дополнительную логику более продуктивно. Кстати, когда я начал работать с миникомпьютерами, разделение не всегда было инструкцией. На некоторых машинах это был вызов библиотеки программного обеспечения, например квадратный корень.
nigel222

Ответы:

34

Разделитель гораздо менее элегантно сопоставляется с типичным оборудованием. В качестве примера возьмем ПЛИС решетки ICE40.

Давайте сравним два случая: этот множитель 8x8 и 16 бит:

module multiply (clk, a, b, result);
   input clk;
   input [7:0]a;
   input [7:0]b;
   output [15:0]result;
   always @(posedge clk)
     result = a * b;
endmodule // multiply

и этот делитель, который уменьшает 8- и 8-битные операнды до 8-битного результата:

module divide(clk, a, b, result);
   input clk;
   input [7:0] a;
   input [7:0] b;
   output [7:0] result;
   always @(posedge clk)
     result = a / b;
endmodule // divide

(Да, я знаю, часы ничего не делают )

Обзор сгенерированной схемы при отображении множителя на ПЛИС ICE40 можно найти здесь, а разделитель - здесь .

Статистика синтеза от Yosys:

умножить

  • Количество проводов: 155
  • Количество битов провода: 214
  • Количество общественных проводов: 4
  • Количество открытых проводных битов: 33
  • Количество воспоминаний: 0
  • Количество бит памяти: 0
  • Количество процессов: 0
  • Количество ячеек: 191
    • SB_CARRY 10
    • SB_DFF 16
    • SB_LUT4 165

делить

  • Количество проводов: 145
  • Количество битов провода: 320
  • Количество общественных проводов: 4
  • Количество открытых проводных битов: 25
  • Количество воспоминаний: 0
  • Количество бит памяти: 0
  • Количество процессов: 0
  • Количество ячеек: 219
    • SB_CARRY 85
    • SB_DFF 8
    • SB_LUT4 126

Стоит отметить, что размер сгенерированного verilog для множителя полной ширины и максимально делительного делителя не так уж и велик. Однако, если вы посмотрите на рисунки ниже, вы заметите, что множитель имеет, возможно, глубину 15, тогда как делитель выглядит примерно как 50 или около того; критический путь (т. е. самый длинный путь, который может возникнуть во время работы) определяет скорость!


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

Умножение

Умножьте на ICE40 (предупреждение: ~ 100 мегапиксельное изображение)

Масштабированное изображение множителя

Делить

( Разделите на ICE40 ) (предупреждение: ~ 100-мегапиксельное изображение)

Масштабированное изображение делителя

Маркус Мюллер
источник
4
нет, вы можете реализовать их не итеративно. Но это просто займет некоторое время, пока действительный результат не «сгладит» в логике. Реализации выше не являются итеративными.
Маркус Мюллер
9
Я хочу настенный плакат делителя.
Ян Хоусон
5
Там в PDF сейчас в умножении изложении. Это 3378 × 3177 мм, поэтому, пожалуйста, обсудите это со своим другом, прежде чем ставить это на потолок спальни.
Маркус Мюллер
2
Ваши 100-мегапиксельные изображения впечатляют, но они излишни для того, что вы пытаетесь сделать, и они создают огромные проблемы для любого, кто пытается просмотреть эту страницу на устройстве с ограниченным объемом памяти, таком как телефон или планшет. Если вы хотите отобразить изображения встроенными, найдите способ предварительного просмотра с меньшим разрешением.
Дэйв Твид
4
Йо, эти графики на графике сняты, йо!
Спенсер Уильямс
8

Медленное деление по своей сути итеративное, поэтому оно занимает больше времени. Есть несколько более быстрые алгоритмы медленного деления, чем простые, использующие таблицы поиска. Алгоритм SRT производит два бита за цикл. Ошибка в такой таблице стала причиной печально известной ошибки Pentium FDIV (около 1994 г.). Тогда есть так называемые быстрые алгоритмы деления.

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

Спехро Пефхани
источник
Но суть в том, что алгоритмы деления нельзя распараллелить, в отличие от алгоритмов умножения, и поэтому они намного медленнее?
Марко Гулин
2
@MarkoGulin «не могу» - очень сильное утверждение. Это конечно не просто.
Спехро Пефхани
2
Я думаю, что вы могли бы ослабить его от «алгоритмов деления нельзя распараллелить» до «способов, которые мы нашли для распараллеливания деления, больше напрягают аппаратное обеспечение, реализующее деление, чем параллельное умножение». Сферо дает пример того, как сделать одноцикловое деление, используя O (2 ^ n) вентилей для умножения n-битных чисел ... но это просто не практично.
Cort Ammon - Восстановить Монику
1
Длинное деление может использовать параллелизм в любой желаемой степени, вычисляя приблизительное обратное значение, которое при умножении на делитель дает результат вида 1000 ... xxxx. При работе с делителем в такой форме с N начальными нулями это легко вычислять N битов результата с каждым шагом.
суперкат
8

Мы можем иметь несколько слоев логики за такт, но есть предел, сколько именно слоев логики у нас может быть, насколько сложными могут быть эти слои, будет зависеть от нашей тактовой частоты и нашего полупроводникового процесса.

Тем не менее, есть много разных алгоритмов умножения, и я понятия не имею, какой из них может использоваться микроконтроллерами

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

  • Сдвиг одного операнда различными значениями
  • Маскирование сдвинутых чисел на основе второго операнда
  • Добавление результатов маскировки вместе.

Итак, давайте посмотрим на реализацию этого в оборудовании.

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

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

Предположим, что полный сумматор реализован в двух «этапах гейта».

  • 1 для маскировки, чтобы получить 8 промежуточных результатов.
  • 2 добавить группы из трех чисел, чтобы уменьшить 8 промежуточных результатов до 6
  • 2 добавить группы из трех чисел, чтобы уменьшить 6 промежуточных результатов до 4
  • 2 добавить группу из трех чисел, чтобы уменьшить 4 промежуточных результата до 3
  • 2 добавить группу из трех чисел, чтобы уменьшить 3 промежуточных результата до 2
  • 32, чтобы сложить два последних результата.

Всего около 46 логических этапов. Большая часть которых потрачена на суммирование двух последних промежуточных результатов.

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

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


С другой стороны, если мы посмотрим на алгоритмы деления, мы обнаружим, что все они имеют итерационный процесс, где.

  1. То, что делается на одной итерации, сильно зависит от результатов предыдущей итерации.
  2. количество логических этапов, необходимых для реализации итерации, примерно пропорционально n (вычитание и сравнение очень похожи по сложности на сложение)
  3. количество итераций также примерно пропорционально n.

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

Питер Грин
источник
Спасибо за ваш ответ. Я читал в вики, что алгоритм Дадды очень эффективен, когда речь идет о необходимом количестве шлюзов для реализации этого алгоритма на оборудовании. Несмотря на это, большая часть оборудования использует «двоичное длинное умножение»?
Марко Гулин
1
Я думаю, что дада algotihm является оптимизированной версией двоичного длинного умножения.
Питер Грин
Я сжигаю 8 циклов, чтобы сделать 1 / х деление. Затем я использую это против умножения на 8 циклов для фиксированной стоимости в 16 циклов.
B Degnan
Это наглядно демонстрирует, что умножение не намного хуже сложения.
Хаген фон
1
Для итерации требуется вычитание, которое может быть выполнено за этапы O (lgN) с использованием аппаратного обеспечения O (NlgN), или этапов O (sqrt (N)) с использованием аппаратного обеспечения O (N). Однако существенным моментом является то, что для умножения требуются стадии O (lgN), а для деления требуются стадии O (NlgN). Не O (N * N), но больше, чем умножение на коэффициент O (N), если только вы не начинаете с того, что берете примерную обратную величину, чтобы можно было выполнить больше работы за шаг.
суперкат
4

Алгоритм деления (фактически любой алгоритм) может быть выполнен за один такт. Если вы готовы платить за дополнительные транзисторы и снизить допустимую тактовую частоту.

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

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

user4574
источник
4

Практические алгоритмы деления основаны на числовых наборах, которые сходятся к частному.

  • Существуют аддитивные методы, такие как невосстановление или СТО, которые работают путем добавления или удаления 2 ^ N к частному и, соответственно, добавления или удаления делителя 2 ^ N * к частичному остатку до тех пор, пока он не достигнет нуля.

  • Существуют мультипликативные методы, такие как метод Ньютона-Рафсона или Гольдшмана, которые являются методами поиска корней, где деление вычисляется как обратное умножению.

Аддитивные методы дают один или несколько битов за цикл. Мультипликативные методы удваивают число битов для каждого цикла, но требуют некоторого начального приближения, часто получаемого с помощью таблицы констант.

«Медленные» и «быстрые» номиналы вводят в заблуждение, так как фактическая скорость зависит от количества битов, от того, сколько оборудования выделено для функции (а быстрый множитель очень велик) ...

Деление медленнее, чем умножение, потому что нет прямого, параллельного метода для его вычисления: либо существует итерация, либо аппаратное обеспечение копируется для реализации итерации в виде каскадных (или конвейерных) блоков.

TEMLIB
источник
0

Почему аппаратное деление занимает намного больше времени, чем умножение на микроконтроллере?

Это не вопрос электроники. В лучшем случае это компьютерный вопрос, лучше адресованный Stack Overflow.

См., Например, здесь: Является ли умножение быстрее, чем деление с плавающей точкой?

В действительности это вопрос из реальной жизни: почему деление занимает намного больше времени, чем умножение?

Что бы вы предпочли посчитать на бумаге?

51 * 82

или

4182 / 51

Деление занимает больше времени, чем умножение, потому что это сложнее сделать .

Ник Гаммон
источник