4 ms·

While you are kind of correct in that a memory channel doesn't do multiple concurrent transfers, single-threaded memory-bound workloads definitely leave signif

by zurn 12y ago

While you are kind of correct in that a memory channel doesn't do multiple concurrent transfers, single-threaded memory-bound workloads definitely leave significant main memory performance on the table in most cases. (And if not memory-bound, then of course a lot more still) Main memory is high-latency, and single threads usually don't saturate the bandwidth because they are not issuing back to back pipelined requests to memory. The CPU has a single shared memory controller and it sees requests from all cores/SMTs. A desktop x86 might support 16 outstanding cache misses that might come from different cores or SMT "threads", and is designed to keep the memory channels busy and request pipelines full by scheduling in work from all the cores/SMTs, doing prefetching according to the big picture etc. Even multiple threads accessing the same data doesn't actually look different from the DIMM point of view, all the x86 synchronization takes place inside the CPU caches and is invisible in the main memory traffic/requests. (This is true even on multi-socket systems, the caches just talk to each other using an inter-CPU bus). Also, desktop/server systems typically have more than one independent memory channel, in beefy servers a whole lot of them

adwn 12y ago
> While you are kind of correct in that a memory channel doesn't do multiple concurrent transfers, single-threaded memory-bound workloads definitely leave significant main memory performance on the table in most cases. You have to distinguish between memory-latency-bound and memory-throughput-bound. If your program has a simple, regular access pattern (which the CPU's prefetcher recognizes), then it's not that hard to saturate the memory bandwidth of a typical two-channel, DDR3-1600 system (25.6 GB/s peak throughput) with a single thread.
- vardump 12y ago
  In order to get maximum throughput, you also might need to do SIMD loads (and stores). On Haswell this means two AVX loads, 64 bytes per clock cycle (two 32 byte loads). I think with with scalar code, you get only 16 bytes per cycle (two 8 byte loads), and 32 bytes per cycle with SSE. So a single Haswell core at 3 GHz can load about 178 GB/s! On Ivy Bridge, SSE is enough to saturate memory bus. Regardless, that's quite a bit more than what lower cache levels and DRAM can supply. It's not very hard to saturate whole CPU-local memory bus with just one core.
  - nkurz 12y ago
    So a single Haswell core at 3 GHz can load about 178 GB/s! On Ivy Bridge, SSE is enough to saturate memory bus. I'd claim instead that it's surprisingly hard to saturate the memory bus with a single core[1]. Presuming your math is right, you've given the rate at which Haswell can load from L1 to registers if we can ignore latency and concurrency. That is, the CPU can sustain this number only if the latency is low enough relative to the number of "requests in flight". In practice, these prevent a single core from saturating the memory bus except for the case of dual-channel memory, perfect prediction and prefetching, and no TLB misses. More commonly, the latency of the read from memory combined with the limited number (10) of "line fill buffers" reduces the throughput from RAM. The formula for actual bandwidth is known as "Little's Law": Concurrency = Latency * Bandwidth. Considering it's fundamental importance in gauging actual performance, it's strikingly rare to see it discussed in CS theory. John McCalpin, the author of the Stream benchmark has an excellent explanation of how it applies to memory bandwidth: http://sites.utexas.edu/jdm4372/2010/11/03/optimizing-amd-opteron-memory-bandwidth-part-1-single-thread-read-only/ http://sites.utexas.edu/jdm4372/2010/11/03/optimizing-amd-op... [1] Here's my write up of trying to do so on Sandy Bridge: https://software.intel.com/en-us/forums/topic/480004 https://software.intel.com/en-us/forums/topic/480004
    - vardump 12y ago
      Your write up was pretty interesting. Especially the instruction mixes, LFENCEs of all things helped?! Thanks. I haven't tried optimize fill / copy rate since late nineties. Getting the last 10-20% appears to be rather tricky. Luckily maximum bandwidth per core is seldom an issue. Sometimes I've thought about designs of having one core do memory prefetching ahead of loosely synchronized other core doing actual computation, to get maximal serial computational throughput. The idea is, that the computational core would fetch data from shared L2/L3 at all times. For those times, when the access patterns are not predictable for hardware prefetcher etc.
      - nkurz 12y ago
        LFENCEs of all things helped I don't really understand what was happening here, but it was a definite positive effect. I think the issue is that the early preloads filled the queue, preventing the stores from happening. The bright side is that getting good performance on Haswell is easier, as it supports 2 loads and 1 store per cycle (although note that address generation is still a bottleneck unless you make sure that the store is using a "simple" address). I've thought about designs of having one core do memory prefetching ahead of loosely synchronized other core doing actual computation I'm interested in this approach too, but haven't really tried it out. "srean" suggested this also: https://news.ycombinator.com/item?id=8711626 https://news.ycombinator.com/item?id=8711626 I think it could would work well if you know your access patterns in advance, the hard part would be keeping the cores in sync. In the absence of real-time synchronization, you'd need a really high throughput queue to make this work. Interesting write up and links here: http://www.infoq.com/articles/High-Performance-Java-Inter-Thread-Communications http://www.infoq.com/articles/High-Performance-Java-Inter-Th... It's a much easier problem if you can batch up the preloads rather than doing them one at a time. I have had success with a somewhat similar technique within a single core by issuing a batch of prefetches, then do processing on the previous data, then a batch of loads corresponding to the prefetches, then repeat. You can get 2-3x improvement of throughput on random access if you are able to tolerate the slightly increased latency. The key is figuring out how to keep the maximum number of requests in flight at all times.

by zurn 12y ago

adwn 12y ago

> While you are kind of correct in that a memory channel doesn't do multiple concurrent transfers, single-threaded memory-bound workloads definitely leave significant main memory performance on the table in most cases. You have to distinguish between memory-latency-bound and memory-throughput-bound. If your program has a simple, regular access pattern (which the CPU's prefetcher recognizes), then it's not that hard to saturate the memory bandwidth of a typical two-channel, DDR3-1600 system (25.6 GB/s peak throughput) with a single thread.

vardump 12y ago
In order to get maximum throughput, you also might need to do SIMD loads (and stores). On Haswell this means two AVX loads, 64 bytes per clock cycle (two 32 byte loads). I think with with scalar code, you get only 16 bytes per cycle (two 8 byte loads), and 32 bytes per cycle with SSE. So a single Haswell core at 3 GHz can load about 178 GB/s! On Ivy Bridge, SSE is enough to saturate memory bus. Regardless, that's quite a bit more than what lower cache levels and DRAM can supply. It's not very hard to saturate whole CPU-local memory bus with just one core.
- nkurz 12y ago
  So a single Haswell core at 3 GHz can load about 178 GB/s! On Ivy Bridge, SSE is enough to saturate memory bus. I'd claim instead that it's surprisingly hard to saturate the memory bus with a single core[1]. Presuming your math is right, you've given the rate at which Haswell can load from L1 to registers if we can ignore latency and concurrency. That is, the CPU can sustain this number only if the latency is low enough relative to the number of "requests in flight". In practice, these prevent a single core from saturating the memory bus except for the case of dual-channel memory, perfect prediction and prefetching, and no TLB misses. More commonly, the latency of the read from memory combined with the limited number (10) of "line fill buffers" reduces the throughput from RAM. The formula for actual bandwidth is known as "Little's Law": Concurrency = Latency * Bandwidth. Considering it's fundamental importance in gauging actual performance, it's strikingly rare to see it discussed in CS theory. John McCalpin, the author of the Stream benchmark has an excellent explanation of how it applies to memory bandwidth: http://sites.utexas.edu/jdm4372/2010/11/03/optimizing-amd-opteron-memory-bandwidth-part-1-single-thread-read-only/ http://sites.utexas.edu/jdm4372/2010/11/03/optimizing-amd-op... [1] Here's my write up of trying to do so on Sandy Bridge: https://software.intel.com/en-us/forums/topic/480004 https://software.intel.com/en-us/forums/topic/480004
  - vardump 12y ago
    Your write up was pretty interesting. Especially the instruction mixes, LFENCEs of all things helped?! Thanks. I haven't tried optimize fill / copy rate since late nineties. Getting the last 10-20% appears to be rather tricky. Luckily maximum bandwidth per core is seldom an issue. Sometimes I've thought about designs of having one core do memory prefetching ahead of loosely synchronized other core doing actual computation, to get maximal serial computational throughput. The idea is, that the computational core would fetch data from shared L2/L3 at all times. For those times, when the access patterns are not predictable for hardware prefetcher etc.
    - nkurz 12y ago
      LFENCEs of all things helped I don't really understand what was happening here, but it was a definite positive effect. I think the issue is that the early preloads filled the queue, preventing the stores from happening. The bright side is that getting good performance on Haswell is easier, as it supports 2 loads and 1 store per cycle (although note that address generation is still a bottleneck unless you make sure that the store is using a "simple" address). I've thought about designs of having one core do memory prefetching ahead of loosely synchronized other core doing actual computation I'm interested in this approach too, but haven't really tried it out. "srean" suggested this also: https://news.ycombinator.com/item?id=8711626 https://news.ycombinator.com/item?id=8711626 I think it could would work well if you know your access patterns in advance, the hard part would be keeping the cores in sync. In the absence of real-time synchronization, you'd need a really high throughput queue to make this work. Interesting write up and links here: http://www.infoq.com/articles/High-Performance-Java-Inter-Thread-Communications http://www.infoq.com/articles/High-Performance-Java-Inter-Th... It's a much easier problem if you can batch up the preloads rather than doing them one at a time. I have had success with a somewhat similar technique within a single core by issuing a batch of prefetches, then do processing on the previous data, then a batch of loads corresponding to the prefetches, then repeat. You can get 2-3x improvement of throughput on random access if you are able to tolerate the slightly increased latency. The key is figuring out how to keep the maximum number of requests in flight at all times.