我们被告知 RAM 内存的抽象是一个长字节数组。对于 CPU 来说,访问它的任何部分都需要相同的时间。能够同时访问 4 GB(在我的计算机上)中的任何字节的设备是什么?因为这对我来说似乎不是一个微不足道的任务。
我问过同事和我的教授,但没有人能指出如何用简单的逻辑门来完成这项任务,如果它不仅仅是逻辑门的棘手组合,那么它是什么?
我个人的猜测是,你可以以 O(log(n)) 的速度实现对任何内存的访问,其中 n 是内存的大小。因为每个门都会将内存分成两部分,并将内存访问指令发送到下一个将内存分成两个门的部分。但这需要很多门。我无法提出任何其他有根据的猜测,我什至不知道我应该在谷歌中查找的设备的名称。
请帮助我痛苦的好奇心,并提前致谢。
编辑
引用你的“RAM可以将值从单元地址X发送到一些输出引脚”,这里是每个人都跳过(再次)对我来说不重要的事情的地方。在我看来,为了构建一个由 64 个引脚决定从 2^64 中获取哪个字节的门,每个引脚需要将整个可能的内存范围一分为二。如果索引 0 处的位为 0 -> 则地址位于内存 0-2^64/2,否则地址位于内存 2^64/2-2^64。依此类推,但是内存获取将经过的门数(我们称之为)将为 64(一个常量)。然而,所需的门数量为 N,其中 N 是内存字节数。
仅仅因为有 64 个引脚,并不意味着您仍然可以将其解码为 2^64 范围内的单次读取。 4GB内存是否带有内存控制中的4GB门???
现在这可以改进,因为随着我越来越多地阅读有关此内存的架构的信息,如果将内存放入具有 sqrt(N) 行和 sqrt(N) 列的矩阵中,则获取内存的门数需要经过的时间是 O(log(sqrt(N)*2) ,所需的门数量是 2*sqrt(N) ,这要好得多,我认为这可能是一个商业秘密。
/编辑
到底是什么,我不妨以此作为答案。
是的,在物理世界中,内存访问不可能是恒定的时间。
但它甚至不能是对数时间。您想到的 O(log n) 电路最终涉及某种二叉(或其他)树,并且您无法在 3D 宇宙中使用恒定长度的电线制作二叉树。
无论您的技术的“每单位体积位数”容量是多少,存储 n 位都需要一个半径为 O(n^(1/3)) 的球体。由于信息只能以光速传播,因此访问球体另一端的一点需要时间 O(n^(1/3))。
但即使这样也是错误的。如果你想谈论我们宇宙的实际局限性物理朋友说 https://physics.stackexchange.com/questions/2281/在任何球体中可以存储的绝对最大位数与球体的表面积成正比,而不是其体积。因此,包含 n 位信息的最小球体的实际半径是 O(sqrt(n))。
正如我在评论中提到的,所有这些都毫无意义。我们通常用来分析算法的计算模型假设访问时间恒定的 RAM,这在实践中足够接近事实,并且允许对竞争算法进行公平的比较。 (尽管致力于高性能代码的优秀工程师非常关心局部性和内存层次结构......)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)