algorithm - 现代处理器如何进行整数算术运算？

Question

This维基百科页面提到了不同数学运算的计算复杂性，包括加法、减法、乘法和除法。我想重点介绍这四个。

首先，每个提到的操作都将其复杂性指定为数字位数的函数。这是否意味着在真实硬件上添加任意两个 int64_t 将花费相同的时间？

这是一个重要的方面，因为它会让攻击者获得一些信息，例如来自纯粹观察加密/解密方的 key 。

添加两个 int32_t 会比添加两个 int64_t 快两倍吗？

此外，乘法和除法运算有多种算法。其中哪些用于现实生活中的处理器？我们知道渐近复杂性，但也有常数，这很重要。

IMUL 指令的英特尔软件开发人员手册没有提及实际使用的算法，只是简单地指出:

TMP_XP ← DEST ∗ SRC

整个问题一开始都与 x86_64 架构有关，但如果有任何其他架构(ARM、Aarch64、POWER)使用与 x86 不同的技术，我会很感兴趣。

Answer 1

Does that mean that on real hardware adding any two int64_ts will take the same amount of time?

如果 CPU 有一个 64 位宽的 ALU ，是的。

我这样定义它是因为仍在设计具有 32 位或更小 ALU 的“现代”处理器，主要用于嵌入式市场。

it would allow an attacker to gain some information about e.g. cryptographic keys from sheer observing the encrypting/decrypting party.

我不确定基于时间的侧信道攻击是否像您问题的前提那样工作。如果与该处理器的真正 64 位版本相比，给定处理器上的 64 位数学运算需要多次运算，则整个算法中的所有整数数学运算都会变慢，因此攻击者将要学习的是他们在功能较弱的处理器上运行它。

由于指令执行率而导致侧信道泄漏的地方是你有 if/else 分支的地方，并且一个分支比另一个分支花费的时间更长，因此从统计上讲，攻击者可以探测以确定哪些输入导致执行更多 if 子句而不是 else 子句，从而收集一些关于 key 或其他信息的信息。

Will adding two int32_ts take twice shorter than adding two int64_ts?

不一定。 64 位处理器可能会同时运行这两种添加。

如果您想问这是否会发生在 32 位处理器上，那么答案是“可能会”，但实际上，您需要在处理器数据手册中查找这些内容。这将为您提供每条指令的时间信息。

您的问题指定了四种不同的架构，您至少缺少一个关键架构(32 位 x86，仍然存在)，并且您还缺少其他几个可能的架构。 (例如 MIPS。)我不准备仔细阅读所有可能的处理器手册并为您查找。

The Intel Software Developer manual for the IMUL instruction doesn't mention the actual algorithm used

不，但它应该以时钟周期数给出计时信息。

可能不会这么简单地说，因为pipelining , caching这也起到了作用。

I'd be interesting if any other architectures (ARM, Aarch64, POWER) use some different techniques than x86.

当然。这方面没有硬性规定。

例如，像 ARM 这样的 RISC 处理器往往需要至少 4 条指令来执行任何类似乘法的操作，因为它们需要一个读取-计算-存储周期，因为所有数学运算都必须在处理器的寄存器中进行。 (读取操作数 1，读取操作数 2，相乘，存储产品。)

对比通常具有内存寻址模式的 CISC 处理器，其中乘法指令可以编码为“将内存位置 A 与内存位置 B 相乘并存储在内存位置 C”。操作数仍然需要加载到 CPU 中并相乘，结果仍然需要存储，但它看起来像一条指令。

CISC 模型还掩盖了 DRAM 读取延迟、缓存时序问题等问题，RISC 模型使这些问题更加明确。

曾几何时，处理器非常简单，您可以轻松回答这样的问题，但我们已经过了几十年。