[math-fun] Scaling of computer memories
[This post is mercifully short.] There are good empirical & theoretical reasons for thinking that the reference locality of computer software scales as M^(-3/2). This means that if one has a least-recently-used (LRU) cache of size M, the "miss ratio" (probability of not getting a cache "hit") is proportional to M^(-1/2).* One problem with analyzing cache behavior is the "lumpiness" of the cache hierarchy. However, LRU behavior can be modeled by a linear *stack*, where each reference *permutes* an address location to the *top* of the stack using a move-to-front strategy. As a result, the entire memory system becomes linearly ordered in LRU fashion.** Once we have a memory in LRU order, the probability of access to the N'th element in the stack is now proportional to N^(-3/2), so we have a more-or-less smooth analytic model of our memory system. We now have the probability of accessing the N'th element, but in order to compute the mean access *latency*, we need to know how memory latency scales with memory size. Thus, expected access time (EAT): EAT = integrate(pr(N)*latency(N),N,1,infinity) where pr(N) is the probability of accessing the N'th item in the LRU stack, and latency(N) is the latency of accessing the N'th item in the LRU stack. But if latency(N) scales as fast as sqrt(N) -- i.e., speed of light on a 2D plane -- then our *integral won't converge*, and our computer will run slower and slower *per memory access* (it grows as log(M)) on larger and larger programs. However, if latency(N) scales like N^(1/3) -- i.e., speed of light in 3D -- then our *integral WILL converge*, and our computer will run at a constant expected time *per memory access*. So we have no choice but to utilize 3D memory systems for large computations. So perhaps this explains why our brains are approximately spherical? Also, this explains why the denizens of Flatland will never achieve true brilliance. * Hartstein, et al. "On the Nature of Cache Miss Behavior": Is It sqrt(2)?". J. Instruction-Level Parallelism 10 (2008), 1-22. ** Mattson, et al. "Evaluation Techniques for Storage Hierarchies", IBM Sys. J. 9, 78 (1970).
participants (1)
-
Henry Baker