3 ms·

A friend of mine is working on a custom memory controller for specialized devices at Google Cloud. The software people are giving the hardware people tremendous

by kccqzy 4y ago

A friend of mine is working on a custom memory controller for specialized devices at Google Cloud. The software people are giving the hardware people tremendous pressure in making sure the memory controller works well with all common powers-of-two strides, besides random strides. There are some (very primitive by software standards) "hash functions" implemented in hardware to make that work. IIRC at that time they treat the relevant bits in an address as a vector in GF(2) and multiply by a certain hardcoded invertible matrix. (Of course there are properties for that matrix besides being invertible.) The idea is that if a single bit in the input address changes, all output bits should have equal probability of flipping and not flipping (the avalanche effect).

anonymoushn 4y ago
This seems pretty wasteful compared to the alternative of writing software that does not use power-of-two strides and deleting this part of the hardware!
- kccqzy 4y ago
  As a cloud provider, you can't ask your customer to rewrite their software in order to run optimally on your cloud.
  - anonymoushn 4y ago
    Do specialized devices at Google Cloud run all sorts of customer software? Do the customers typically target other CPUs that have this extra stuff in their cache?
- Sirened 4y ago
  Rewriting software is often significantly more expensive (or, not even possible when dealing with third party code!) whereas with hardware you can fix it once for everyone and see a large speed up across the entire system.
ggrrhh_ta 4y ago
The Power7 (2010) already had a very powerful prefetching engine (also programmable) able to detect a multitude of patterns/striding supporting even 12 different streams. Its design, composability and not only automatic detection but its programmability, allowing you to drive its behavior or change according to different computation phases made a fantastic piece of engineering for its time: https://www.redbooks.ibm.com/redbooks/pdfs/sg248079.pdf https://www.redbooks.ibm.com/redbooks/pdfs/sg248079.pdf Just pointing this out (there are several generations of Power's with improved design) as you mentioned memory controllers. The problem in the blog post is different (aliasing) and I guess that all I can say is that unless some randomness is introduced, every design will have a "worst" access pattern.
pclmulqdq 4y ago
Under the hood, this hashing has existed for a long time, certainly since Haswell at Intel. However, Intel designed it to make sequential access still mostly sequential, and combined it with prefetch logic that is decent at detecting strided access if you poke it the right way. Also, main memory has a different hash than L3 cache does, and this hash is designed for sequential access.
- anonymoushn 4y ago
  Can I read more about this somewhere? On Haswell I've observed a 5% speedup (for a whole program that mostly does a bunch of other work) from spacing a bunch of arrays that are typically all pretty small and all accessed consecutively all the way through to have their start positions differ by some amount of cache lines other than a power of 2. So it certainly seemed to me like I was working with a set-associative cache where power of 2 strides were pathological.
majke 4y ago
Ok, so you are talking about rowhammer. Let me try to put this in my own words. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf https://people.freebsd.org/~lstewart/articles/cpumemory.pdf DRAM is using hardware technology that is hard. Each dram bit can be addressed by ranks, banks, chips rows and columns. Depending on stuff, you typically read/load a whole cache line from DRAM. This is nice and easy. However, AFAIU there is delay needed in the chip after reading bytes. This means a read to subsequent cache line would be slow. Therefore, there is a strong reason to lay out subsequent data far away, ideally on different chips. So you can read cache line #0 that can be on some physical chip #A and if you read line #1 it should not be on chip #A but ideally on a "random" other physical die. This mapping, of "physical memory address" into actually where the data is on the DDRAM, is very much a hash function. This is usually done by the CPU manufacturer I guess. See the reversing of sandy bridge algo: https://lackingrhoticity.blogspot.com/2015/04/l3-cache-mapping-on-sandy-bridge-cpus.html https://lackingrhoticity.blogspot.com/2015/04/l3-cache-mappi... Rowhammer is an attack, where the attacker targets a single physical chip of DRAM and cause its misbehaviour due to keeping it active in unusal patterns. RowHammer is basically about reversing that hashing and exploiting the shortcuts dram manufacturers took when producing the chips. https://blog.cloudflare.com/every-7-8us-your-computers-memory-has-a-hiccup/ https://blog.cloudflare.com/every-7-8us-your-computers-memor... But this is about DRAM. I don't know how it works in Cache, but I don't think there is a special hashing algo. It just uses middle bits to address the cache line, as the parent article says.
- remram 4y ago
  This is very interesting but doesn't really seem related to the comment you replied to?
  - oso2k 4y ago
    It is related because a naïve program will access a device (CPU registers, instruction pipelines, indirect cache access, RAM, disk, optical disk) in a linear fashion. RAM no longer has linear or near linear access. Disk drives of all types dealt with rotation speed, spindle head speed, etc. For a long time, disk specs were recorded in linear/sequential access time, full seek access time, and average random access time until sequential access time became less than 1ms and OSes/disk cache programs made average random access time the only latency worth caring about. In summary, most storage devices have hierarchical performance and it’s worth caring about how to optimize for that.

by kccqzy 4y ago

anonymoushn 4y ago

This seems pretty wasteful compared to the alternative of writing software that does not use power-of-two strides and deleting this part of the hardware!

kccqzy 4y ago
As a cloud provider, you can't ask your customer to rewrite their software in order to run optimally on your cloud.
- anonymoushn 4y ago
  Do specialized devices at Google Cloud run all sorts of customer software? Do the customers typically target other CPUs that have this extra stuff in their cache?
Sirened 4y ago
Rewriting software is often significantly more expensive (or, not even possible when dealing with third party code!) whereas with hardware you can fix it once for everyone and see a large speed up across the entire system.

ggrrhh_ta 4y ago

The Power7 (2010) already had a very powerful prefetching engine (also programmable) able to detect a multitude of patterns/striding supporting even 12 different streams. Its design, composability and not only automatic detection but its programmability, allowing you to drive its behavior or change according to different computation phases made a fantastic piece of engineering for its time: https://www.redbooks.ibm.com/redbooks/pdfs/sg248079.pdf https://www.redbooks.ibm.com/redbooks/pdfs/sg248079.pdf Just pointing this out (there are several generations of Power's with improved design) as you mentioned memory controllers. The problem in the blog post is different (aliasing) and I guess that all I can say is that unless some randomness is introduced, every design will have a "worst" access pattern.

pclmulqdq 4y ago

Under the hood, this hashing has existed for a long time, certainly since Haswell at Intel. However, Intel designed it to make sequential access still mostly sequential, and combined it with prefetch logic that is decent at detecting strided access if you poke it the right way. Also, main memory has a different hash than L3 cache does, and this hash is designed for sequential access.

anonymoushn 4y ago
Can I read more about this somewhere? On Haswell I've observed a 5% speedup (for a whole program that mostly does a bunch of other work) from spacing a bunch of arrays that are typically all pretty small and all accessed consecutively all the way through to have their start positions differ by some amount of cache lines other than a power of 2. So it certainly seemed to me like I was working with a set-associative cache where power of 2 strides were pathological.

majke 4y ago

Ok, so you are talking about rowhammer. Let me try to put this in my own words. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf https://people.freebsd.org/~lstewart/articles/cpumemory.pdf DRAM is using hardware technology that is hard. Each dram bit can be addressed by ranks, banks, chips rows and columns. Depending on stuff, you typically read/load a whole cache line from DRAM. This is nice and easy. However, AFAIU there is delay needed in the chip after reading bytes. This means a read to subsequent cache line would be slow. Therefore, there is a strong reason to lay out subsequent data far away, ideally on different chips. So you can read cache line #0 that can be on some physical chip #A and if you read line #1 it should not be on chip #A but ideally on a "random" other physical die. This mapping, of "physical memory address" into actually where the data is on the DDRAM, is very much a hash function. This is usually done by the CPU manufacturer I guess. See the reversing of sandy bridge algo: https://lackingrhoticity.blogspot.com/2015/04/l3-cache-mapping-on-sandy-bridge-cpus.html https://lackingrhoticity.blogspot.com/2015/04/l3-cache-mappi... Rowhammer is an attack, where the attacker targets a single physical chip of DRAM and cause its misbehaviour due to keeping it active in unusal patterns. RowHammer is basically about reversing that hashing and exploiting the shortcuts dram manufacturers took when producing the chips. https://blog.cloudflare.com/every-7-8us-your-computers-memory-has-a-hiccup/ https://blog.cloudflare.com/every-7-8us-your-computers-memor... But this is about DRAM. I don't know how it works in Cache, but I don't think there is a special hashing algo. It just uses middle bits to address the cache line, as the parent article says.

remram 4y ago
This is very interesting but doesn't really seem related to the comment you replied to?
- oso2k 4y ago
  It is related because a naïve program will access a device (CPU registers, instruction pipelines, indirect cache access, RAM, disk, optical disk) in a linear fashion. RAM no longer has linear or near linear access. Disk drives of all types dealt with rotation speed, spindle head speed, etc. For a long time, disk specs were recorded in linear/sequential access time, full seek access time, and average random access time until sequential access time became less than 1ms and OSes/disk cache programs made average random access time the only latency worth caring about. In summary, most storage devices have hierarchical performance and it’s worth caring about how to optimize for that.