Как современные процессоры выполняют целочисленные арифметические операции?

Означает ли это, что на реальном оборудовании добавление любых двух int64_t займет одинаковое количество времени?

Если ЦП имеет 64-битное ALU, да.

Я определяю это так, потому что есть «современные» процессоры с 32-битными или меньшими ALU, которые все еще разрабатываются, в основном для рынка встраиваемых систем.

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

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

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

Добавление двух int32_t займет в два раза меньше времени, чем добавление двух int64_t?

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

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

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

В руководстве Intel Software Developer для инструкции IMUL не упоминается фактический используемый алгоритм.

Нет, но он должен давать информацию о времени в количестве тактовых циклов.

Это, вероятно, не будет сформулировано так просто, потому что конвейерная обработка, кеширование и тому подобное также играют роль.

Было бы интересно, если бы какие-либо другие архитектуры (ARM, Aarch64, POWER) использовали какие-то методы, отличные от x86.

Конечно. Жестких правил в этой сфере нет.

Например, процессоры RISC, такие как ARM, как правило, требуют не менее 4 инструкций для выполнения чего-либо вроде умножения, потому что им требуется цикл чтения-вычисления-сохранения, поскольку все математические операции должны выполняться в регистрах процессора. (Чтение операнда 1, чтение операнда 2, умножение, сохранение произведения.)

В отличие от процессора CISC, который часто имеет режимы адресации памяти, где инструкция умножения может быть закодирована как «умножить ячейку памяти A на ячейку памяти B и сохранить в ячейке памяти C». Операнды по-прежнему должны быть загружены в ЦП и перемножены, и результат по-прежнему должен быть сохранен, но это выглядит как одна инструкция.

Модель CISC также маскирует такие вещи, как задержки чтения DRAM, проблемы синхронизации кэша и т. д., которые модель RISC делает более явными.

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

Означает ли это, что на реальном оборудовании добавление любых двух int64_ts займет одинаковое количество времени?

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

Будет ли добавление двух int32_ts вдвое короче, чем добавление двух int64_ts?

Это зависит, например, операции x64 SIMD позволяют добавлять четыре 32-битных целых числа за одну операцию, опять же с потенциально несколькими операциями за такт. Поэтому, если ваш код можно векторизовать для использования этого, вы можете обнаружить, что добавление четырех пар 32-битных целых чисел займет столько же времени, сколько добавление двух пар 64-битных целых чисел. (Целые числа не будут int32_t, но будут использовать векторизованные типы SIMD). Если вы используете скалярное ALU в x64, то я подозреваю, что это займет одинаковое время, независимо от того, есть ли у вас 32- или 64-битные числа в регистрах, но не можете найти ссылку.

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

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

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