algorithm - 目的是通过内存操作将 MMIX 汇编中的最低有效位设置为 0？

Question

在 MMIX 机器的文档中 mmix-doc第 3 页第 4 段:

We use the notation to stand for a number consisting of consecutive bytes starting at location . (The notation means that the least significant t bits of k are set to 0, and only the least 64 bits of the resulting address are retained. ...

Answer 1

符号 M_2^t[k] 只是一种形式符号，用于表示可被 2^{t 整除的地址}.

这在定义后立即得到确认

All accesses to 2^t-byte quantities by MMIX are aligned, in the sense that the first byte is a multiple of 2^t.

大多数架构，特别是 RISC 架构，要求内存访问对齐，这意味着地址必须是访问大小的倍数。
因此，例如，从内存中读取 64 位字(MMIX 表示法中的八进制)需要地址能被 8 整除，因为 MMIX 内存是字节可寻址的⁽¹⁾，并且一个字节中有 8 个字节。八.

如果所有可能的数据大小都是 2 的幂，我们会看到一种模式出现:

Multiples of     Multiples of     Multiples of
   2                 4                 8

 0000               0000              0000
 0010               0100              1000
 0100               1000
 0110               1100
 1000
 1010
 1100
 1110

2 = 2¹ 的倍数的最低位始终设置为零⁽²⁾，4 = 2² 的倍数具有最低两位设置为零，8 的倍数 = 2³ 最低三位设置为零，依此类推。

一般来说，2^t 的倍数中至少 t 位设置为零。
您可以通过归纳法来正式证明这一点。t。

对齐 64 位数字(MMIX 地址空间的大小)的一种方法是清除其较低的 t 位，这可以通过执行 AND 来完成使用以下形式的掩码进行操作

11111...1000...0
\      / \    /
 64 - t     t

这样的掩码可以表示为2⁶⁴ - 2^t。

2⁶⁴ 是一个很大的数字，我们假设地址空间只有 2⁵。
假设我们有二进制地址 17h 或 10111b，并且希望将其与八进制对齐。
八进制是 8 个字节，2³，因此我们需要清除低 3 位并保留其他 2 位。
要使用的掩码是十六进制的 11000b 或 18h。这个数字是 2⁵-2³ = 32 - 8 = 24 = 18 小时。
如果我们在 17h 和 18h 之间执行 bool AND，我们会得到 10h，这是对齐的地址。

这解释了之后不久使用的符号 k ∧ (2⁶⁴ − 2^t)，“楔形”符号∧是逻辑AND。
所以这个符号只是“描绘”对齐地址k所需的步骤。

请注意，还引入了符号 k ∨ (2^t − 1)，这是互补的，∨ 是 OR，整个效果是具有较低的t 位设置为 1。
这是大小为 2^t 的对齐访问占用的最大地址。
符号本身用于解释字节序。

---

如果您想知道为什么对齐访问很重要，它与硬件实现有关。
长话短说，尽管内存是可字节寻址的，例如 64 位，但 CPU 与内存的接口(interface)具有预定义的大小。
因此，CPU 以 64 位 block 的形式访问内存，每个 block 从 64 位的倍数地址开始(即在 8 字节上对齐)。 访问未对齐的位置可能需要CPU执行两次访问:

CPU reading an octa at address 2, we need bytes at 2, 3, 4 and 5.

Address    0 1 2 3 4 5 6 7 8 9 A B ...
           \     / \     /
              A       B

CPU read octa at 0 (access A) and octa at 4 (access B), then combines the two reads.

RISC 机器倾向于避免这种复杂性并完全禁止未对齐的访问。

---

⁽¹⁾ 引用:“如果 k 是任何无符号八字节，则 M[k] 是 1 字节 数量”。

⁽²⁾ 2⁰ = 1 是 2 的唯一奇数次幂，因此您可以猜测，通过删除它，我们只能得到偶数。