Почему сложение происходит так же быстро, как побитовые операции в современных процессорах?

73

Я знаю, что побитовые операции выполняются очень быстро на современных процессорах, потому что они могут работать на 32 или 64 битах параллельно, поэтому побитовые операции занимают только один такт. Однако сложение - это сложная операция, которая состоит как минимум из одной и, возможно, до дюжины побитовых операций, поэтому я, естественно, думал, что она будет в 3-4 раза медленнее. Я был удивлен, увидев после простого теста, что сложение происходит так же быстро, как и любая побитовая операция (XOR, OR, и т. Д.). Кто-нибудь может пролить свет на это?

анонимное
источник
1
Да, умножение было довольно быстрым в моих тестах тоже. Это было только примерно в 2 раза медленнее, чем сложение, в то время как деление было примерно в 30 раз (!) Медленнее.
Аноним
Компактный обзор современных параллельных сумматоров префиксного дерева: таксономия параллельных префиксных сетей Дэвида Харриса: pages.hmc.edu/harris/research/taxonomy.pdf
Франки
Более детально: докторская диссертация доктора Чен Чен «Структуры с параллельным префиксом для двоичных и сумматорных {2n − 1, 2n, 2n + 1} сумматоров» digital.library.okstate.edu/etd/Chen_okstate_0664D_10070.pdf
Франки

Ответы:

104

Добавление происходит быстро, потому что разработчики ЦП установили схему, необходимую для его быстрого выполнения. Это занимает значительно больше гейтов, чем побитовые операции, но достаточно часто, чтобы разработчики ЦП посчитали, что оно того стоит. См. Https://en.wikipedia.org/wiki/Adder_(electronics) .

Оба могут быть сделаны достаточно быстро, чтобы выполнить в течение одного цикла процессора. Они не одинаково быстры - сложение требует большего количества затворов и большей задержки, чем побитовая операция, - но достаточно быстро, чтобы процессор мог сделать это за один такт. Для каждой логики декодирования команд и управления есть издержки задержки для каждой инструкции, и задержка для этого значительно больше, чем задержка для выполнения побитовой операции, поэтому разница между этими двумя значениями уменьшается. Ответ AProgrammer в и ответ Paul92 в объяснить эти эффекты хорошо.

DW
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
DW
38

Есть несколько аспектов.

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

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

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

AProgrammer
источник
6
+1. Да, большинство процессоров работают с тактовой частотой, но несколько часовых процессоров имеются в продаже.
Дэвид Кэри
2
Другая возможность состоит в том, что процессор может хранить 64-битный регистр как один 16-битный фрагмент и три 17-битных фрагмента, где дополнительные биты каждого фрагмента содержат отложенный перенос снизу. Для добавления, которое сопровождается побитовой операцией или сохранением, может потребоваться 1-2 дополнительных цикла для распространения переноса, но добавление, за которым следует другое добавление, не будет. Кроме того, в случае «хранилища» дополнительное время распространения может задержать производительность хранилища, но не будет необходимости в коде, «ожидающем» его.
суперкат
3
@supercat Pentium 4 сделал что-то вроде этого, с двойной скоростью (относительно остальной части процессора) ALU, которая будет иметь младшие 16 или 32 бита, готовые для последующей операции, за половину цикла до битов верхней половины.
Джеффри Босбом
2
Вы уверены, что измеряете то, что хотите? В этом случае вывод ОП из измерений оказывается правильным для подавляющего большинства процессоров. Добавление настолько распространено, что суперскалярные процессоры имеют дополнительные модули на всех исполнительных портах, а логические значения настолько дешевы в реализации (по количеству транзисторов), что они также присутствуют на всех портах. Так что add и boolean почти всегда имеют одинаковую пропускную способность (например, 4 на такт в Intel Haswell).
Питер Кордес
2
Целочисленное добавление SIMD часто ниже пропускной способности, чем логическое значение SIMD, хотя они обычно имеют одинаковую задержку. Процессоры Intel от PentiumII до Broadwell могут запускать только добавления вектора (например paddw) со скоростью 2 на тактовую частоту, а логические значения (например pand) - 3 на тактовую частоту. (Skylake размещает векторный сумматор на всех трех портах векторного исполнения.)
Питер Кордес
24

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

Например, простой процессор может иметь 3 шага для каждой инструкции: извлечь, выполнить и сохранить. В любое время обрабатываются 3 инструкции: одна извлекается, одна выполняется, а другая сохраняет результаты. Это называется конвейером и имеет в этом примере 3 этапа. Современные процессоры имеют конвейеры с более чем 15 ступенями. Однако сложение, как и большинство арифметических операций, обычно выполняется за один этап (я говорю об операции добавления двух чисел с помощью АЛУ, а не о самой инструкции - в зависимости от архитектуры процессора, инструкция может потребовать больше циклов для извлечения аргументов из памяти, выполнения условий, сохранения результатов в памяти).

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

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

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

Paul92
источник
3
Большие издержки от более длинных конвейеров - больше циклов, чтобы оправиться от неправильного предсказания ветви! В настоящее время затраты транзисторов для буферизации данных между этапами незначительны. Даже простой конвейерный процессор должен извлекать / декодировать перед выполнением фактически выполняемых инструкций. Если ЦП обнаруживает, что интерфейс работал над неправильным кодом, потому что ветвление пошло не так, как он предсказывал (или из-за других неправильных предположений), он должен отбросить эту работу и начать с правильной инструкции. Ситуация ухудшается только с суперскалярными неработающими процессорами, которые могут иметь много insns в полете.
Питер Кордес
12

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

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

Обратите внимание, что простая инструкция MOV (регистр-регистр) выполняет даже меньше вычислений, чем побитовая логика, однако и MOV, и ADD обычно занимают один цикл. Если бы MOV можно было сделать в два раза быстрее, процессоры работали бы в два раза быстрее, а ADD были бы двумя циклами.

Джеймс Холлис
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Жиль "ТАК - перестань быть злым"
1
Краткое изложение обсуждения: некоторые неработающие процессоры обрабатывают MOV специально с переименованием регистров с практически нулевой задержкой. См. Может ли x86 MOV действительно быть «бесплатным»? Почему я не могу воспроизвести это вообще? для полной информации о том, что MOV действительно стоит.
Питер Кордес
12

Дополнение достаточно важно, чтобы не ожидать, пока бит переноса пройдет через 64-битный аккумулятор: термин для этого - сумматор переноса с переносом, и они в основном являются частью 8-битных процессоров (и их ALU) и выше. Действительно, современным процессорам, как правило, также не требуется намного больше времени выполнения для полного умножения: на самом деле инструмент переноса информации является действительно старым (и сравнительно доступным) инструментом в наборе инструментов разработчика процессоров.

user72735
источник
Целочисленное умножение определенно имеет большую задержку и меньшую пропускную способность, чем ADD на x86. Но это удивительно быстро, учитывая, сколько сумматоров требуется для построения быстрого множителя: например, на Intel с Nehalem и AMD с Ryzen, 8/16/32/64-битное скалярное целочисленное умножение имеет задержку в 3 цикла, по одному на пропускную способность 1c (один полностью конвейерный исполнительный блок). Это отстой по сравнению с пропускной способностью ADD 3 или 4 за такт, но удивительно по сравнению с 9-тактной задержкой IMUL в Intel Pentium P5. Аналогично для SIMD: умножение вектора на int имеет большую задержку и меньшую пропускную способность, чем сложение, но все же быстро.
Питер Кордес
Так что да, умножение раньше было намного дороже по сравнению с другими инструкциями, чем сейчас. Избегать его более чем за две инструкции обычно не стоит, а иногда даже замена из двух инструкций не стоит (например, с помощью leaинструкции shift + add ).
Питер Кордес
9

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

(Цикл инструкций, а не тактовый цикл - например, 6502 занимает минимум два тактовых цикла на инструкцию из-за того, что он не конвейеризован и не имеет кэша команд)

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

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

pjc50
источник
Это не управляемые пользователем побитовые операции, но некоторые инструкции на 8086 (например, очистка флага прерывания ) занимали меньше циклов, чем целочисленное сложение. Более абстрактно, система RISC, где все инструкции имеют одно слово, могла бы использовать простой двоичный счетчик для ПК, который был бы намного более быстрой схемой, чем сумматор общего назначения.
Марк
Добавление на счетчике программ, как правило, очень простое по сравнению с арифметической инструкцией сложения, поскольку один из операндов мал (либо размер инструкции, либо относительное смещение перехода, которое также ограничено по размеру)
Бен Фойгт,
6502 был конвейерным - он считывал первый байт следующей инструкции во время последнего цикла предыдущего. Иначе выборка / декодирование / выполнение были бы по крайней мере тремя циклами.
gnasher729
8

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

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

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

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

Корт Аммон
источник
7

Современные процессоры синхронизируются: каждая операция занимает некоторое целое число тактов. Конструкторы процессора определяют длительность тактового цикла. Здесь есть два соображения: во-первых, скорость аппаратного обеспечения, например, измеренная как задержка одного NAND-шлюза. Это зависит от используемой технологии и таких компромиссов, как скорость и энергопотребление. Это не зависит от конструкции процессора. Во-вторых, разработчики решают, что длина тактового цикла равна n задержкам одиночного NAND-шлюза, где n может быть 10, или 30, или любым другим значением.

Этот выбор n ограничивает, насколько сложными могут быть операции, которые могут быть выполнены за один цикл. Там будут операции, которые могут быть выполнены за 16, но не с 15 задержками NAND. Таким образом, выбор n = 16 означает, что такая операция может быть выполнена в цикле, выбор n = 15 означает, что она не может быть выполнена.

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

Теперь ваш вопрос: сложение и вычитание являются настолько распространенными операциями, что вы хотите иметь возможность выполнять их за один цикл. В результате не имеет значения, что AND, OR и т. Д. Могут выполняться быстрее: им все еще нужен этот один цикл. Конечно, у устройства, «вычисляющего» И, ИЛИ и т. Д., Есть много времени, чтобы крутить пальцы, но с этим ничего не поделаешь.

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

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

gnasher729
источник
6

Позвольте мне исправить несколько вещей, которые не были упомянуты явно в ваших существующих ответах:

Я знаю, что побитовые операции выполняются очень быстро на современных процессорах, потому что они могут работать на 32 или 64 битах параллельно,

Это правда. Обозначение процессора как «XX» бит обычно (не всегда) означает, что большинство его общих структур (ширина регистров, адресуемая RAM и т. Д.) Имеют размер XX бит (часто «+/- 1» или что-то подобное). Но, что касается вашего вопроса, вы можете с уверенностью предположить, что ЦП с 32-битным или 64-битным выполнит любую основную битовую операцию с 32 или 64-битным в постоянное время.

поэтому побитовые операции занимают только один тактовый цикл.

Этот вывод не обязательно так. Особенно процессоры с богатыми наборами команд (google CISC vs. RISC) могут легко занять более одного цикла даже для простых команд. При чередовании даже простые команды могут быть разбиты на fetch-exec-store с 3 часами (как пример).

Однако сложение является сложной операцией

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

он состоит как минимум из одной и, возможно, до десятка битовых операций, поэтому я, естественно, думал, что это будет в 3-4 раза медленнее.

Это займет в 3-4 раза больше транзисторов, но по сравнению с большой картиной, которой можно пренебречь.

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

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

Если вы хотите добавить больше битов, чем ваша архитектура процессора, вы понесете штраф за необходимость делать это поэтапно. Но это на другом уровне сложности (уровень языка программирования, а не уровень сборки / машинного кода). В прошлом это было распространенной проблемой (или сегодня на небольших встроенных процессорах). Для ПК и т. Д. Их 32 или 64 бита достаточно для наиболее распространенных типов данных, чтобы это стало спорным вопросом.

Anoe
источник
Интересно отметить, что сокращение временных затрат на добавление от O (N) к O (sqrt (N)) не приводит к значительному увеличению требуемого количества транзисторов или сложности маршрутизации (на каждом этапе просто нужно, чтобы один проводник проходил снизу) и должны быть sqrt (N) дополнительные этапы слияния. Стоимость времени может быть уменьшена до O (lgN) за счет O (lgN) транзисторов, но во многих случаях может быть полезно обрабатывать что-то вроде 64- добавление битов, как, например, восемь 8-битных добавлений (с использованием переадресации sqrtN), соединенных с тремя уровнями логики слияния, а не как 64-битные добавления с шестью уровнями слияния
суперкат
Да, сумматоры довольно просты. Что действительно впечатляет, так это современные x86-процессоры с полностью конвейерным 64-разрядным целочисленным множителем с 3-тактной задержкой . (например, imul rax, rcxимеет задержку 3c и пропускную способность по одному на 1c в семействе Intel Sandybridge и AMD Ryzen). Даже 64-битное полное умножение (производящее 128-битный результат в rdx: rax) имеет одинаковую задержку и пропускную способность, но реализовано как 2 мопа (которые работают параллельно на разных портах). (См. Agner.org/optimize для таблиц инструкций и отличного руководства по микроархам).
Питер Кордес
[add-with-carry] находится на другом уровне сложности (уровень языка программирования, а не уровень ассемблера / машинного кода . Это зависит от языка. Компилятор AC, нацеленный на 16-битный ЦП, должен генерировать add / adc для вас при компиляции добавление двух uint32_tзначений. Это по-прежнему актуально для int64_t для 32-разрядных целей. AVR - это 8-разрядный RISC-микроконтроллер, поэтому для 32-разрядных целых чисел требуется 4 инструкции: godbolt.org/g/wre0fM
Питер Кордес
Да, @PeterCordes, вот что я имел в виду, я немного прояснил свое предложение.
AnoE