3 ms·

I wonder if PCs will ever have non-linear memory. To explain what I mean, suppose you have a big 2-dimensional array in memory. As it works now, if you read a

by tomerv 14y ago

I wonder if PCs will ever have non-linear memory. To explain what I mean, suppose you have a big 2-dimensional array in memory. As it works now, if you read a cell from memory, the area in memory around it is brought into the cache. Because of the way that arrays are represented in memory, what you get in the cache is just cells from the same row (or column). This means that if you need to access neighboring cells above of below the current cell you're not making any use of the cache. The way I see it, it might be useful if the system could somehow instruct the memory to bring a different-shaped block into the cache. Maybe there will be a whole part of memory intended for 2-dimensional arrays, and where blocks of memory will be allocated as squares on the plane (instead of segments on a line). Of course, something like this would require support from the programming language, which would need to mark put 2-dimensional arrays in that special part of the memory (and allocation will be much harder, now that you need to allocate 2-dimensional chunks).

ajross 14y ago
That kind of caching architecture exists for graphics hardware already. GPUs have modes where the natural breakdown of memory is 2D (basically by interleaving the X and Y bits), and indeed that improves cache locality for 2D accesses. But not by a whole lot. The reason caches come in "lines" that are bigger than the words size of the processor is not an optimization (i.e. they're not deliberately bringing in nearby memory in the hope that it will be useful). The reason is that the logic associated with maintaining the cache (index and tag bits) is expensive, and needs to be repeated for each "thing" you have in the cache. So by making the "things" bigger (e.g. the 512 bit cache line on modern CPUs) you reduce the overhead of the bookkeeping.
- Someone 14y ago
  "The reason caches come in "lines" that are bigger than the words size of the processor is not an optimization (i.e. they're not deliberately bringing in nearby memory in the hope that it will be useful)." I do not think that is true. There is considerable chance that that extra memory will be useful. The simplest example to think of are cache lines that contain program code. The other canonical example is the "for item in array do item = f(x)" loop.
  - ajross 14y ago
    No, there's hardware to do that too (speculative reads), but it's even more complicated. Really the driver of cache line size is simple efficiency. Software has to jump through lots of hoops in practice to try to align accesses to cache lines, and that could be avoided if memory could be efficiently cached in word-sized chunks.
    - Someone 14y ago
      I still doubt that. IMO, cache lines are larger than the largest item a CPU can read because the probability that the extra data will be needed soon is high enough to offset the extra work needed to read that larger cache line and the (few) transistors needed to increase cache line size. In some sense, large cache lines are just cheap ways to implement speculative reads. See for example http://dl.acm.org/citation.cfm?id=255272 http://dl.acm.org/citation.cfm?id=255272 (pay walled, but the abstract is clear enough): "A significant observation is that, although increasing line sizes can result in a higher hit ratio, it also considerably increases traffic to main memory, thereby degrading the performance."
Someone 14y ago
Not what you describe, but tries to solve the same problem: PowerPC has instructions that tell the system what memory you are planning to use. See for example https://developer.apple.com/hardwaredrivers/ve/caches.html https://developer.apple.com/hardwaredrivers/ve/caches.html There also are CPUs that attempt to detect access patterns without help from the programmer, for example Power: http://chipdesignmag.com/display.php?articleId=3926&issueId=37 http://chipdesignmag.com/display.php?articleId=3926&issu.... I think Intel CPUs have similar functionality, but these were the ones I found first (using "cache stride hints" as Google query), perhaps because Intel uses different terminology.

by tomerv 14y ago

ajross 14y ago

That kind of caching architecture exists for graphics hardware already. GPUs have modes where the natural breakdown of memory is 2D (basically by interleaving the X and Y bits), and indeed that improves cache locality for 2D accesses. But not by a whole lot. The reason caches come in "lines" that are bigger than the words size of the processor is not an optimization (i.e. they're not deliberately bringing in nearby memory in the hope that it will be useful). The reason is that the logic associated with maintaining the cache (index and tag bits) is expensive, and needs to be repeated for each "thing" you have in the cache. So by making the "things" bigger (e.g. the 512 bit cache line on modern CPUs) you reduce the overhead of the bookkeeping.

Someone 14y ago
"The reason caches come in "lines" that are bigger than the words size of the processor is not an optimization (i.e. they're not deliberately bringing in nearby memory in the hope that it will be useful)." I do not think that is true. There is considerable chance that that extra memory will be useful. The simplest example to think of are cache lines that contain program code. The other canonical example is the "for item in array do item = f(x)" loop.
- ajross 14y ago
  No, there's hardware to do that too (speculative reads), but it's even more complicated. Really the driver of cache line size is simple efficiency. Software has to jump through lots of hoops in practice to try to align accesses to cache lines, and that could be avoided if memory could be efficiently cached in word-sized chunks.
  - Someone 14y ago
    I still doubt that. IMO, cache lines are larger than the largest item a CPU can read because the probability that the extra data will be needed soon is high enough to offset the extra work needed to read that larger cache line and the (few) transistors needed to increase cache line size. In some sense, large cache lines are just cheap ways to implement speculative reads. See for example http://dl.acm.org/citation.cfm?id=255272 http://dl.acm.org/citation.cfm?id=255272 (pay walled, but the abstract is clear enough): "A significant observation is that, although increasing line sizes can result in a higher hit ratio, it also considerably increases traffic to main memory, thereby degrading the performance."

Someone 14y ago

Not what you describe, but tries to solve the same problem: PowerPC has instructions that tell the system what memory you are planning to use. See for example https://developer.apple.com/hardwaredrivers/ve/caches.html https://developer.apple.com/hardwaredrivers/ve/caches.html There also are CPUs that attempt to detect access patterns without help from the programmer, for example Power: http://chipdesignmag.com/display.php?articleId=3926&issueId=37 http://chipdesignmag.com/display.php?articleId=3926&issu.... I think Intel CPUs have similar functionality, but these were the ones I found first (using "cache stride hints" as Google query), perhaps because Intel uses different terminology.