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

Сегодня я наткнулся на этот отрывок:

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

Мне любопытно, почему побитовые операции были немного быстрее, чем операции сложения / вычитания на старых микропроцессорах.

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

Я знаю, что и арифметические, и побитовые операции на современных процессорах выполняются за один цикл, но, говоря чисто о времени распространения для схемы, теоретически сохраняется ли задержка в современных процессорах?

Наконец, у меня возник концептуальный вопрос C о выполнении операции побитового сдвига:

unsigned x = 1;
x <<= 5;

unsigned y = 0;
y += 32;

И x, и y должны содержать значение 32, но потребовалось ли 5 отдельных сдвигов влево, чтобы получить x к этому значению (как, например, побитовые сдвиги, реализованные через каналы)? Чтобы уточнить, я спрашиваю исключительно о поведении схемы, а не о количестве тактов.


c cpu-architecture bit-manipulation digital-logic bitwise-operators
person Vilhelm Gray    schedule 27.03.2013    source источник
comment
Ваш первый пример дает ноль, но, вероятно, это была опечатка. Остальная часть вашего вопроса относится к оборудованию и, возможно, не по теме.   -  person 500 - Internal Server Error    schedule 28.03.2013
comment
@ 500 Я думаю, что важно знать, как работает процессор, чтобы вы могли лучше понять, как работает высокоуровневый код.   -  person kjprice    schedule 28.03.2013
comment
@kjprice: Достаточно честно - вы заметите, что я не голосовал за закрытие.   -  person 500 - Internal Server Error    schedule 28.03.2013
comment
@ 500-InternalServerError Спасибо за предупреждение, я скорректировал код, чтобы он был правильным. :)   -  person Vilhelm Gray    schedule 28.03.2013
comment
@VilhelmGray Я знаю, что и арифметические, и побитовые операции выполняются в течение одного цикла на современных процессорах. Умножение происходит медленнее, чем, например, побитовое смещение, поэтому ваше утверждение не верно для каждой операции.   -  person    schedule 27.09.2017
comment
Побитовые операции, которые могут быть быстрее на старых процессорах, будут AND / OR / XOR, а не сдвиги более чем на 1. Цилиндрический сдвигатель, который может выполнять сдвиги на 1 цикл для произвольного числа сдвигов, дороже, чем предварительный перенос сумматор. (например, посмотрите на Pentium4: сдвигается медленно, но add так же быстро, как xor. agner.org/optimize/. ) Сдвиг на 1, тем не менее, был бы разумным примером; многие простые процессоры поддерживают сдвиги только на 1 или требуют 1 цикла на счет.   -  person Peter Cordes    schedule 01.05.2018

Ответы (6)


arrow_upward
26
arrow_downward

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

Например, крайний левый бит 01111111 + 00000001 равен 1, а крайний левый бит 01111110 + 00000001 равен 0.

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

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

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

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

person Eric Postpischil    schedule 27.03.2013

arrow_upward
4
arrow_downward

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

Таким образом, вы получаете наивное решение - N раз Full-Adders где N - ширина вашего ALU в битах.

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

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

Если вам нужна дополнительная информация, вам, вероятно, нужно будет спросить об этом на http://electronics.stackexchange.com.

person Earlz    schedule 27.03.2013
comment
Если вы подумаете о том, как будет реализована таблица поиска с ее демультиплексорами, выбирающими сигнал, который комбинируется с сигналом от другого операнда, в одном из вентилей 2 ^ N, которые снова подаются в мультиплексор, вы поймете, что полностью комбинаторный сумматор - это просто таблица поиска, сильно оптимизированная, чтобы избавиться от всей повторяющейся логики. - person Bernd Jendrissek; 14.05.2013
comment
@BerndJendrissek В какой-то момент все сводится к поисковой таблице. См. Также Тактическое ядро ​​логического дизайна - person Earlz; 14.05.2013

arrow_upward
2
arrow_downward

Чтобы ответить на ваш последний вопрос, это зависит от обстоятельств. Некоторые архитектуры имеют сдвиги только на 1 (например, z80), некоторые архитектуры предоставляют сдвиги на более крупные константы и / или переменные, но реализуют их внутри как набор "сдвигов на 1" (например, старые реализации x86), есть некоторые архитектуры, которые могут сдвигаться более чем на 1 за один цикл, но только если величина сдвига является постоянной, есть некоторые архитектуры (например, современные реализации x86), которые используют баррель-сдвиг и может сдвигаться на переменную за один цикл, и есть еще больше возможностей.

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

person harold    schedule 28.03.2013
comment
Ага, побитовые операции, которые потенциально быстрее, чем add, - это такие вещи, как and / xor. Стволовые переключатели дороже (или менее важны), чем сумматоры, по крайней мере, так решили дизайнеры Pentium4. - person Peter Cordes; 01.05.2018

arrow_upward
0
arrow_downward

Некоторые реализации сложения должны выполнять дополнительный цикл для бита переноса. Например: 16-битное целое число требует нескольких инструкций на 8-битном процессоре. Это также относится к сдвигу. Но сдвиг всегда может сдвинуть биты высоты на младшие биты следующего байта. Сложение должно добавить нижний бит в дополнительном раунде.

person Lukas    schedule 27.03.2013

arrow_upward
-1
arrow_downward

Побитовый оператор выполняется за меньшее время, потому что

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

Вот почему сдвиг битов выполняется быстрее, чем другие арифметические операции.

person Abdul Rehman    schedule 27.03.2013
comment
Побитовые операции, такие как and / xor / or, тоже всегда быстрые. Конечно, mul / div дорого стоит, но здесь спрашивают о побитовом и добавлении / подпрограмме. - person Peter Cordes; 01.05.2018

arrow_upward
-2
arrow_downward

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

Наверное, кто-то сможет ответить на этот вопрос точнее и основательнее.

person kjprice    schedule 27.03.2013