RAM如何以O(1)速度访问内存中的任何位置 [英] How is RAM able to acess any place in memory at O(1) speed

问题描述

我们被告知，RAM存储器的抽象是一长字节数组.而且对于CPU来说，访问它的任何部分都需要花费相同的时间.什么设备可以同时访问4 GB的任何字节(在我的计算机上)?对我来说，这似乎不是一件容易的事.

We are taught that the abstraction of the RAM memory is a long array of bytes. And that for the CPU it takes the same amount of time to access any part of it. What is the device that has the ability to access any byte out of the 4 gigabytes (on my computer) in the same time? As this does not seem as a trivial task for me.

我问过同事和教授，但是没有人能确切指出如何通过简单的逻辑门来完成这项任务，如果这不仅是逻辑门的棘手组合，那又是什么?

I have asked colleagues and my professors, but nobody can pinpoint to the how this task can be achieved with simple logic gates, and if it isn't just a tricky combination of logic gates, then what is it?

我个人的猜测是，您可以以O(log(n))的速度实现对任何内存的访问，其中n是内存的大小.因为每个门会将内存分成两部分，然后向您发送内存访问指令，以便下一个将内存分成两门.但这需要大量的大门.我无法提出其他任何有根据的猜测，而且我什至都不知道我应该在Google中查找的设备名称.

My personal guess is that you could achieve the access of any memory in O(log(n)) speed, where n would be the size of memory. Because each gate would split the memory in two and send you memory access instruction to the next split the memory in two gate. But that requires ALOT of gates. I can't come up with any other educated guess, and I don't even know the name of the device that I should look up in Google.

请帮助我激起好奇心，并在此先感谢.

Please help my anguished curiosity, and thanks in advance.

edit< 这就是我学到的！

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是内存字节数.

quote from yours "the RAM can send the value from cell addressed X to some output pins", here is where everyone skip (again) the thing that is not trivial for me. The way that I see it, In order to build a gate that from 64 pins decides which byte out of 2^64 to get, each pin needs to split the overall possible range of memory into two. If bit at index 0 is 0 -> then the address is at memory 0-2^64/2, else address is at memory 2^64/2-2^64. And so on, However the amout of gates (lets call them) that the memory fetch will go through will be 64, (a constant). However the amount of gates needed is N, where N is the number of memory bytes there are.

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

Just because there is 64 pins, it doesn't mean that you can still decode it into a single fetch from a range of 2^64. Does 4 gigabytes memory come with a 4 gigabytes gates in the memory control???

现在这可以改善，因为随着我越来越疯狂地阅读到有关该存储器的结构的信息，如果将存储器放入具有sqrt(N)行和sqrt(N)列的矩阵中，则门的数量取回内存将需要经过的是O(log(sqrt(N)* 2)并且所需的门数量将是2 * sqrt(N)，这要好得多，我认为它可能是商业秘密.

now this can be improved, because as I read furiously more and more about how this memory is architectured, if you place the memory into a matrix with sqrt(N) rows and sqrt(N) columns, the amount of gates that a fetch memory will need to go through is O(log(sqrt(N)*2) and the amount of gates that will be required will be 2*sqrt(N), which is much better, and I think that its probably a trade secret.

/edit<

/edit<

推荐答案

我到底是怎么想的呢?

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

Yes, in the physical world, memory access cannot be constant time.

但它甚至不能是对数时间.您想到的O(log n)电路最终会涉及某种二叉树(或其他任何一种)，并且您无法在3D Universe中用恒定长度的导线制作二叉树.

But it cannot even be logarithmic time. The O(log n) circuit you have in mind ultimately involves some sort of binary (or whatever) tree, and you cannot make a binary tree with constant-length wires in a 3D universe.

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

Whatever the "bits per unit volume" capacity of your technology is, storing n bits requires a sphere with radius O(n^(1/3)). Since information can only travel at the speed of light, accessing a bit at the other end of the sphere requires time O(n^(1/3)).

但是，这是错误的.如果您想谈论宇宙的实际局限性，请物理学朋友说您可以存储的绝对最大位数在任何球体中，它与球体的表面积成正比，而不是其体积.因此，包含n位信息的最小球面的实际半径为O(sqrt(n)).

But even this is wrong. If you want to talk about actual limitations of our universe, our physics friends say the absolute maximum number of bits you can store in any sphere is proportional to the sphere's surface area, not its volume. So the actual radius of a minimal sphere containing n bits of information is O(sqrt(n)).

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

As I mentioned in my comment, all of this is pretty much moot. The models of computation we generally use to analyze algorithms assume constant-access-time RAM, which is close enough to the truth in practice and allows a fair comparison of competing algorithms. (Although good engineers working on high-performance code are very concerned about locality and the memory hierarchy...)

这篇关于RAM如何以O(1)速度访问内存中的任何位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！