Почему деление намного сложнее, чем другие арифметические операции?

39

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

Phonon
источник

Ответы:

34

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

aterrel
источник
2
Раньше и умножение, и деление были медленными операциями. В настоящее время умножение немного быстрее (но немного медленнее, чем сложение / вычитание), но деление все еще медленнее, чем другие. Я полагаю, что Ньютон-Рафсон все еще используется большинством для возвратно-поступательного числа.
JM
12
(Не по теме: «Обратные операции, как правило, трудны. Просто посмотрите на интеграцию или дифференцирование.» - зависит от того, что вы делаете - символьное или числовое. Дифференцирование символически легко, но численно сложно; интеграция символически трудно, но численно легко.)
JM
1
Хорошо, я справлюсь, сказав, что кубатура - это другая банка червей; но, по крайней мере, в одномерном случае квадратура легче дифференцирования.
JM
1
В любом случае, инверсии всегда идут парами. Почему вы называете одну «операцией», а другую «обратной»?
Дэвид Кетчон
2
Ни итерация, ни обратное не усложняют. Трудность деления происходит из-за того, что вы должны сдвинуть результат с частного до остатка, используя евклидову меру. См. Теорему об алгоритме деления .
20

Хотя все современные процессоры, по-видимому, используют итеративный подход, как предлагает aterrel , была проделана некоторая работа над неитеративными подходами. Точность деления с плавающей точкой и квадратного корня с переменной точностью говорит о не итеративной реализации деления с плавающей точкой и квадратного корня в FPGA с использованием справочных таблиц и расширения ряда Тейлора.

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

Почему это не осуществимо?

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

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

Умножение с плавающей запятой сделало этот переход от итеративного к неитеративному десятилетие назад. В наши дни однократное умножение и даже умножение-накопление являются обычным явлением даже в мобильных процессорах.

Прежде чем он стал эффективным использованием бюджета транзисторов, умножение, как и деление, часто выполнялось итерационным методом. Тогда специализированные процессоры DSP могли бы посвятить большую часть своего кремния одному блоку быстрого умножения (MAC) . Процессор Core2duo имеет задержку умножения с плавающей запятой 3 (значение получается из конвейера 3 цикла после его ввода ), но может иметь 3 умножения в полете за раз, что приводит к пропускной способности за один цикл, в то время как его модуль SSE2 может откачивать несколько множителей FP за один цикл.

Вместо того, чтобы выделять огромные области кремния для одного цикла деления, современные процессоры имеют несколько модулей, каждый из которых может выполнять операции параллельно, но оптимизирован для своих конкретных ситуаций. В самом деле, когда вы учитываете SIMD инструкции , такие как SSE или CPU интегрированной графики в Sandy Bridge или более поздней версии процессора, может быть много таких чисел с плавающей запятой делят блоки на CPU.

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

Марк Бут
источник
Насколько мне известно, ни один чип не имеет задержек деления одного цикла для числа с плавающей запятой. Например, в таблицах инструкций Agner Fog для процессоров Intel, AMD и VIA DIVPS (SSE-упакованное деление с плавающей запятой) указывается как 10-14 циклов. Я не могу найти какое-либо оборудование с инструкциями деления на один цикл, но я был бы готов ошибиться. Насколько я могу судить, это не так часто.
Билл Барт
@ Билл - Спасибо, ты прав. Я уверен, что раньше я видел операции деления с одним циклом в микросхемах DSP, поэтому предположил, что он бы прошел путь к рабочему столу, точно так же, как это произошло с умножением за один цикл, но сейчас я не могу найти никаких ссылок. Я обновил свой ответ и добавил некоторую соответствующую информацию о неитеративных методах, которые, возможно, позволят это в будущем. Удивительно думать, что деление сейчас не более эффективно за цикл, чем когда я пользовался транспьютерами.
Марк Бут
1
Я думаю, что DSP делают это, ограничивая диапазон, в котором они точны. Это та же стратегия, что и для поиска + интерполяции для квадратного корня.
Мэтт Кнепли
1
Я не уверен, какова будет задержка такого деления. На частоте 4 ГГц выполнение обхода для справочной таблицы в течение N циклов серьезно ограничивает потенциальный размер упомянутой таблицы (например, кэши L1 стагнируют по 32 Кбайт каждый). Переход на 3D помог бы увеличить это (но это сложно с охлаждением). Есть ли у вас какие-либо идеи о том, какую задержку можно достичь для современных процессоров 4 ГГц / 5 ГГц?
Матье М.
1
Для divps / divpd против числа задержки и пропускной способности mulps / mulpd, смотрите разделение с плавающей запятой против умножения с плавающей запятой . Я взял данные из таблиц инструкций Agner Fog и отформатировал их в виде сводки по размерам div и multi, а также по пропускной способности и задержке, для одинарного или двойного и для различной ширины вектора SIMD. (Чипы Intel обычно имеют SIMD-делитель, который составляет только половину ширины других векторных ALU.)
Питер Кордес,