memory - RAM 如何以 O(1) 的速度访问内存中的任何位置

Question

我们被告知 RAM 存储器的抽象是一个长字节数组。对于 CPU 来说，访问它的任何部分都需要相同的时间。能够同时访问 4 GB(在我的计算机上)中的任何字节的设备是什么？因为这对我来说似乎不是一项微不足道的任务。

我问过同事和我的教授，但没有人能指出如何用简单的逻辑门来完成这项任务，如果它不仅仅是逻辑门的巧妙组合，那它是什么？

我个人的猜测是，您可以以 O(log(n)) 的速度访问任何内存，其中 n 是内存的大小。因为每个门都会将内存一分为二，然后将内存访问指令发送到下一个将内存一分为二的门。但这需要很多门。我想不出任何其他有根据的猜测，我什至不知道应该在 Google 中查找的设备名称。

请帮助我痛苦的好奇心，并提前致谢。

edit< This is what I learned!

引用您的“RAM 可以将地址为 X 的单元格中的值发送到某些输出引脚”，这里是每个人(再次)跳过对我来说不是微不足道的事情的地方。在我看来，为了构建一个由 64 个引脚决定要获取 2^64 中的哪个字节的门，每个引脚需要将整个可能的内存范围分成两个。如果索引 0 处的位为 0 -> 则地址位于内存 0-2^64/2，否则地址位于内存 2^64/2-2^64。依此类推，但是内存获取将通过的门数(让我们称之为)将是 64，(一个常数)。然而，所需的门数量是 N，其中 N 是内存字节数。

仅仅因为有 64 个引脚，并不意味着您仍然可以将其解码为 2^64 范围内的单个提取。 4 GB 内存在内存控制中是否带有 4 GB 门？？？

现在这可以改进，因为随着我越来越多地阅读有关该内存如何构建的信息，如果将内存放入具有 sqrt(N) 行和 sqrt(N) 列的矩阵中，则获取内存的门数将需要通过 O(log(sqrt(N)*2) 并且所需的门数量将是 2*sqrt(N)，这要好得多，我认为这可能是商业 secret 。

/edit<

Answer 1

什么鬼，我不妨把这个作为一个答案。

是的，在物理世界中，内存访问不可能是恒定时间。

但它甚至不能是对数时间。您想到的 O(log n) 电路最终涉及某种二叉(或其他)树，并且您无法在 3D 宇宙中制作具有恒定长度电线的二叉树。

无论您的技术的“单位体积位数”容量是多少，存储 n 位都需要一个半径为 O(n^(1/3)) 的球体。由于信息只能以光速传播，因此访问球体另一端的一点需要时间 O(n^(1/3))。

但即使这样也是错误的。如果你想谈论我们宇宙的实际局限性，我们的 physics friends say您可以在任何球体中存储的绝对最大位数与球体的表面积成正比，而不是与它的体积成正比。所以包含 n 位信息的最小球体的实际半径是 O(sqrt(n))。

正如我在评论中提到的，所有这些都没有实际意义。我们通常用于分析算法的计算模型假设访问时间恒定的 RAM，这在实践中已经足够接近事实，并且可以公平地比较竞争算法。 (尽管从事高性能代码的优秀工程师非常关心局部性和内存层次结构......)