I'm reading through a short paper about hitting the memory wall and I'm struggling to understand how exactly said wall will be hit.

The equation for average access time is fairly simple Tavg = p x Tc + (1-p) x Tm. (Tc = time for cache, Tm = time for DRAM mem, P = probability of cache hit)

What I don't understand is how as Tc and Tm diverge, we hit a wall. I recognize that Tc grows exponentially faster than Tm eventually Tm will play little to no role in access time, but it seems like me that average access time would then just continually increase. I can't seem to understand how a wall is hit.

Would anyone with a sharper mind or keener eye than mine help me to understand this concept?


You have it backwards. $t_m$ is what's growing exponentially relative to $t_c$. Or rather, $t_c$ is decreasing exponentially at a rate faster than $t_m$. $t_c$ and $t_m$ are the times the accesses take which gets smaller as the speeds improve. So, as the paper states, eventually memory performance, i.e. $t_m$ comes to dominate.

The "wall" is the point where having a faster processor, i.e. reducing $t_c$, makes essentially no difference to overall performance. The situation is an example of Amdahl's law. You are correct that things would improve as $t_m$ improves but look at the extreme scenario. Choose $t_c=0$, i.e. computation takes no time at all which is to say we have "infinitely fast" processors. Even with these magical processors, our programs would still run at some multiple of the memory bandwidth. In other words, at some point, if you have a slow program, buying a faster processor will not help. Or, put a different way, at some point, the exponential improvement in processor speeds will be meaningless. It will make no actual difference in program speeds.

And by "at some point", I mean a point we seemingly reached five or ten years ago. Modern (and not so modern) high-performance software design is significantly about, in the terms of this paper, reducing $1-p$. Many of the ideas suggested at the end of that paper have been adopted in some form. Multi-level memory hierarchies make even single processors look like non-uniform memory access architectures. Prefetching and careful data layout help increase cache hits, i.e. increase $p$. We're definitely much happier using designs that waste space if they can reduce cache misses. For example, if we have an object that optionally contains another object, we might store this as a dense array of pairs of the objects with a dummy object as the second when it doesn't exist. This is likely to reduce cache misses as compared to chasing pointers. (However, filling cache and/or cache lines with dummy data also can increase cache misses which is why this kind of design needs a lot of care.) Another way to decrease the effective $t_m$ and benefit from the extra computation speed is to store data compressed. When this saga unfolded with respect to disk v. RAM, it was faster to store inverted indexes for full-text databases utilizing compression and decompress them because the time spent decompressing the indexes was more than made up in the time saved in disk traffic. I can easily imagine a near future where RAM stores a compressed representation of, say, a cache line which gets decompressed transparently by the CPU.

  • $\begingroup$ Wonderfully explained! I totally forgot about amhdals law $\endgroup$
    – Podo
    May 23 '18 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.